1258-Agri-Net

問題（外部リンク）

1258 -- Agri-Net

実装の概要

グラフ全体での最小コストを求める問題です。今回の実装ではクラスカル法を使いました。
クラスカル法の計算量は頂点数をE, 辺の数をVとするとです。今回は密グラフなので辺の数はそれなりに多いですが十分間に合います。

クラスカル法の実装にはUnionFind木を利用します。必要なクラスは載せておきましたのでこれから作る方は参考にしてください。

地味に気をつけなければならない点として、ある行の入力が1行に収まっているとは限りません。
そのため読み込み方を工夫しないと正しく値を読めないことがあるので注意してください。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner scan = new Scanner(System.in);

		while(true){
			//今回は入力終了を示す値が決められていない
			if(!scan.hasNextInt()){
				break;
			}

			int n = scan.nextInt();
			ArrayList<Edge> edges = new ArrayList<Edge>();

			//ある行の入力が1行に収まっているとは限らないが
			//n*n個であることは保証されている
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					int cost = scan.nextInt();

					if(j <= i){
						continue;
					}
					edges.add(new Edge(i,j, cost));
				}
			}

			System.out.println(kruskal(edges, n));
		}
	}


	static final int INF = Integer.MAX_VALUE;


	//クラスカル法
	static long kruskal(ArrayList<Edge> edges, int n){
		int numOfEdge = edges.size();

		Collections.sort(edges);

		DisjointSet set = new DisjointSet(n);

		long result = 0;

		for(int i = 0; i < numOfEdge ; i++){
			Edge tmpEdge = edges.get(i);

			if(!set.isSameSet(tmpEdge.from, tmpEdge.to)){
				set.union(tmpEdge.from, tmpEdge.to);
				result += tmpEdge.cost;
			}
		}

		return result;

	}
}

class DisjointSet {
	private int n;
	private int[] p;
	private int[] rank;

	public DisjointSet(int n){
		this.n = n;

		p = new int[n + 1];
		rank = new int[n + 1];

		for(int i = 1; i <= n; i++){
			makeSet(i);
		}
	}

	private void makeSet(int x){
		p[x] = x;
		rank[x] = 0;
	}

	public void union(int x, int y){
		link (findSet(x), findSet(y));
	}

	private int findSet(int x){
		if(x != p[x]){
			p[x] = findSet( p[x]);
		}
		return p[x];
	}

	public boolean isSameSet(int x, int y){
		return findSet(x) == findSet(y);
	}

	private void link(int x, int y){
		if(rank[x] > rank[y]){
			p[y] = x;
		}
		else {
			p[x] = y;
			if(rank[x] == rank[y]){
				rank[y]++;
			}
		}
	}
}

class Edge implements Comparable<Edge>{
	int from;
	int to;
	int cost;

	Edge(int from, int to, int cost){
		this.from = from;
		this.to = to;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge e) {
		return this.cost - e.cost;
	}
}