AOJ Network Mess

問題

無向木であらわされる、コンピュータとスイッチのネットワークがある。
スイッチは全て木の内点であり、コンピュータは木の葉である。

全てのコンピュータは、それぞれただ一つのスイッチとつながっていて、
全てのスイッチには少なくとも一つのコンピュータがつながっている。

今、コンピュータ同士のネットワーク上の距離行列が与えられる。

元のネットワークでのスイッチに相当する頂点を、次数の小さい順に並べて出力せよ。

制約条件

コンピュータの数≦50
コンピュータ同士の距離は30以下

方針

0〜i番目のコンピュータまでを使ったネットワークがわかっているとき、
i+1番目のコンピュータがどこに入るかは、距離行列から一意に定まる。
n≦50と小さいので、全通り試しても余裕で間に合う。

なので全通り試す。
これをi = 0からはじめてn-1まで順に繰り返せばいい。

ソースコード

int n, m, d[1000][1000];
vi e[1000];
map<int, int> to;
int dist[1000], num[1000];

int main()
{
	while(cin >> n, n){
		m = 0;
		to.clear();
		rep(i, 1000) e[i].clear();
		rep(i, 1000) num[i] = -1;
		rep(i, n) rep(j, n) cin >> d[i][j];
		
		to[0] = m++;
		num[0] = 0;
		for(int i = 1; i < n; i++){
			rep(j, m){
				rep(k, m) dist[k] = -1;
				dist[j] = 0;
				int len = -1;
				queue<int> q;
				q.push(j);
				while(!q.empty()){
					int c = q.front();
					q.pop();
					if(num[c] >= 0){
						if(len < 0){
							len = d[i][num[c]] - dist[c] - 2;
							if(len < 0) goto FAIL;
						}
						else if(len != d[i][num[c]] - dist[c] - 2) goto FAIL;
					}
					rep(k, e[c].size()) if(dist[e[c][k]] < 0){
						dist[e[c][k]] = dist[c] + 1;
						q.push(e[c][k]);
					}
				}
				rep(k, len){
					e[j].pb(m); e[m].pb(j);
					j = m++;
				}
				to[i] = j; num[j] = i;
				break;
				FAIL:;
			}
		}
		
		int deg[1000] = {};
		rep(i, m) deg[i] = e[i].size();
		fr(i, to) deg[i->second]++;
		vi ans;
		rep(i, 1000) if(deg[i]) ans.pb(deg[i]);
		sort(all(ans));
		rep(i, ans.size()) cout << ans[i] << (i == (int)ans.size() - 1 ? "\n" : " ");
	}
	return 0;
}