kmjp's blog

競技プログラミング参加記です

Codeforces #270 Div1 D. Design Tutorial : Inverse the Problem

単純だがなかなか面白かった。
http://codeforces.com/contest/472/problem/D

問題

N個の点の距離を示す行列D[i][j]が与えられる。
N点を(N-1)個の距離付無向辺で連結して木を作る場合、頂点間の最短距離がD[i][j]となる木の作り方は可能か答えよ。

解法

まず、D[i][j]としてあり得ない以下のケースを先に除外する。

  • D[i][i]が非0
  • D[i][j]がi!=jなのに0
  • D[i][j] != D[j][i]

単純な解法は、D[i][j]から最小全域木を作ったうえで頂点間の距離を求め、元のD[i][j]に戻るか調べる方法がある。

自分の解法は以下の通り。
各頂点iを0番からの距離D[0][i]でソートし、0番を根として順次各頂点がどの頂点を親としてつながるか決めていく。
D[0][j]+D[j][i]==D[0][i]となるjがあれば、頂点jは頂点0と頂点iの間にある。
また、jが複数ある場合はD[j][i]が最小となるjを選ぶと、i番目の頂点はj番の子になる。
あとはi番をj番の子としたとき、すでに木にある頂点xがD[x][i]==D[x][j]+D[j][i]かチェックすればよい。

最小全域木は辺をソートするのでO(N^2*logN)かかるけど、自分の方法はO(N^2)で速いはず。

int N;
ll D[2001][2001];
vector<pair<int,int> > V;
vector<int> F;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(x,N) FOR(y,N) cin>>D[x][y];
	FOR(x,N) if(D[x][x]!=0) return _P("NO\n");
	FOR(x,N) FOR(y,N) if(D[x][y]!=D[y][x]) return _P("NO\n");
	FOR(x,N) FOR(y,N) if(x!=y && D[x][y]==0) return _P("NO\n");
	for(x=1;x<N;x++) V.push_back(make_pair(D[0][x],x));
	
	sort(V.begin(),V.end());
	F.push_back(0);
	ITR(it,V) {
		int cur=it->second;
		int best=-1;
		ITR(it,F) if(D[0][*it]+D[*it][cur]==D[0][cur]) {
			if(best==-1 || D[*it][cur]<D[best][cur]) best=*it;
		}
		if(best==-1) return _P("NO\n");
		ITR(it,F) if(D[*it][best]+D[best][cur]!=D[*it][cur]) return _P("NO\n");
		F.push_back(cur);
	}
	_P("YES\n");
}

まとめ

最小全域木で良かったのか…。
まぁ自分の解法もそんな複雑な解じゃないのでいいけど。