Codeforces #270, D : Design Tutorial: Inverse the Problem

問題文

　http://codeforces.com/contest/472/problem/D

問題概要

　 の行列 が与えられる。
　 頂点からなる木であって、頂点 間の距離が となるものは存在するか？
　なお構成される木は、無向・重み付きであって、辺重みは全て正である。

解法

　後の処理を簡単にするために、すぐに分かる条件は先に弾きます。無向グラフなので、 は かつ かつ を満たさなければ木は存在しません。この条件を満たすという条件下で、木を作れるか否か考えていきます。
　 を隣接行列を見做すと 頂点の完全グラフを得られます。このグラフを以降 と書きます。さて、 上の最も短い辺で結ばれた二点は、目的の木に於いて直接辺で結ばれていなければなりません。これは、 が直接結ばれていないとすると、中継する点 が存在して、 となりますが、これは に於いて を結ぶ辺が最短であるという条件に矛盾するということから示されます。残った辺についても同様に考えていくと、Kruskal 法っぽい何かが見えてきて、最小全域木（ MST ）と関連がありそう、という気分になります。
　実際、構成が可能ならば、構成される木は の MST になっていなければなりません。先程と同じような議論ですが、木が MST でないとすると、どこかの辺を付け替えて MST を得ることができるはずです。新しく張られる辺が に於いて二点 を結んでいるとすると、その重みは 未満でなければ前提に矛盾しますが、これは の定義に矛盾します。従って、そのような辺は存在できず、仮定は誤りで木は MST になっているはずと分かります。
　ここまでの考察で、 の MST を一つ求めて、MST 上の距離を表す行列が と一致するかを調べることで問題を解くことができると分かりました。全点間最短距離が必要になっていますが、これはは Prim 法と同時に計算することで全体を で処理できます。構成途中の MST に辺 を加えたとき（点 が新たに MST に加わる点であると一般性を損なわず仮定する）、各頂点 に関して、 と を で更新することができます。 かかる更新処理が 回発生するので、更新処理のオーダーは になります。完全グラフの MST なので Prim 法は で実装した方がオーダーが軽くなり、全体でも となります。

コード

using VI = vector<int>; using VVI = vector<VI>;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using LIM = numeric_limits<T>;

template < typename T > inline void input_n( VT< T > &out, const int N ) { out.resize( N ); copy_n( istream_iterator< T >( cin ), N, out.begin() ); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

constexpr int INF = LIM<>::max() / 2;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VVI G( n );
	FOR( row, G )
	{
		input_n( row, n );
	}

	REP( i, 0, n )
	{
		if ( G[i][i] )
		{
			cout << "NO" << endl;
			return 0;
		}

		REP( j, 0, i )
		{
			if ( G[i][j] <= 0 || G[i][j] != G[j][i] )
			{
				cout << "NO" << endl;
				return 0;
			}
		}
	}

	VI costs = G[0], prev( n );
	VVI distance( n, VI( n, INF ) );			
	VT< bool > used( n );

	while ( true )
	{
		int u = -1, p = -1;
		REP( i, 0, n )
		{
			if ( !used[i] && ( u == -1 || costs[i] < costs[u] ) )
			{
				u = i;
				p = prev[u];
			}
		}

		if ( u == -1 )
		{
			break;
		}

		used[u] = true;
		distance[u][u] = 0;

		REP( v, 0, n )
		{
			distance[v][u] = distance[u][v] = min( distance[u][v],  distance[v][p] + G[p][u] );

			if ( G[u][v] < costs[v] )
			{
				costs[v] = G[u][v];
				prev[v] = u;
			}
		}
	}

	cout << ( distance == G ? "YES" : "NO" ) << endl;

	return 0;
}