Topcoder SRM 492 div2 1000 "TimeTravellingSalesman"

問題：http://www.topcoder.com/stat?c=problem_statement&pm=11049

プラクティス．

都市をつなぐ道とその道を通るコストのリストが与えられる．訪れた都市に簡単に戻れるタイムマシンをもったサラリーマンがすべての都市を巡るための最小のコストを求める．

本番では最小全域木だと思い，手っ取り早くクラスカル法のクラスをサクッとコピペ．サンプルは通ったけど，最初の提出ではコストの合計の型がintだということに気付き再提出．しかしシステムテストでFail．グラフが連結であるかどうかは位数==サイズ-1であるのに，本番ではすべての頂点を通ったかで判定していた（グラフが連結していない場合でアウト）．

import java.util.*;

public class TimeTravellingSalesman {
	public long determineCost(int N, String[] roads) {
		Kruskal k = new Kruskal(N);
		for(String str : concat(roads).split(" ")){
			String[] strs = str.split(",");
			int u = new Integer(strs[0]), v = new Integer(strs[1]), c = new Integer(strs[2]);
			k.addEdge(u, v, c);
			k.addEdge(v, u, c);
		}
		long r = 0;
		List<int[]> edges = k.getEdges();
		if(edges.size() != N - 1){
			return -1;
		}
		for(int[] is : edges){
			r += is[2];
		}
		return r;
	}
	
	String concat(String... suppliedWord) {
		StringBuilder s = new StringBuilder();
		for (String word : suppliedWord) {
			s.append(word);
		}
		return s.toString();
	}



	static class Kruskal {
		int n;
		List<int[]> edges;
		UnionFind uf;

		public Kruskal(int n) {
			this.n = n;
			edges = new ArrayList<int[]>();
		}

		void addEdge(int u, int v, int cost) {
			edges.add(new int[] { u, v, cost });
		}

		List<int[]> getEdges() {
			Collections.sort(edges, new Comparator<int[]>() {
				public int compare(int[] o1, int[] o2) {
					return o1[2] - o2[2];
				}
			});
			uf = new UnionFind(n);
			List<int[]> result = new ArrayList<int[]>();
			for (int[] edge : edges) {
				if (!uf.isSame(edge[0], edge[1])) {
					uf.unite(edge[0], edge[1]);
					result.add(edge);
				}
			}
			return result;
		}
	}
	static class UnionFind {
		int[] par;
		int[] rank;

		public UnionFind(int n) {
			par = new int[n];
			rank = new int[n];
			for (int i = 0; i < n; ++i) {
				par[i] = i;
				rank[i] = 0;
			}
		}

		int find(int x) {
			return (par[x] == x) ? x : (par[x] = find(par[x]));
		}

		void unite(int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y)
				return;
			if (rank[x] < rank[y]) {
				par[x] = y;
			} else {
				par[y] = x;
				if (rank[x] == rank[y])
					++rank[x];
			}
		}

		boolean isSame(int x, int y) {
			return find(x) == find(y);
		}
		
	}
}