2224-Save your cats

問題（外部リンク）

Save your cats | Aizu Online Judge

実装の概要

問題の条件を言い換えると、「与えられたグラフから閉路が無くなるように辺を取り除く場合、取り除いた辺の長さの総和の最小値はいくらか」ということになります。
そのため、クラスカル法を用いて試しに最"大"全域木を作ってみてその辺の長さの総和を計算し、与えられた全ての辺の総和から引き算をすることで答えを出すことができます。
例として、問題ページの最初の例では長さがそれぞれ3,4,5の辺で三角形が作られており、この中で最大全域木を作ると選ばれるのは長さが4,5の辺なので長さ3の辺を除けば閉路はなくなります。
2つ目の例ではそもそも閉路が無いため、最大全域木はもともとのグラフと一致し取り除く辺は1つもないということになります。
なお、今回は閉路さえ出来なければよいのでもともとのグラフが連結でなかったとしてもクラスカル法で特に問題なく解くことができます（試してはいませんがプリム法だと解けないかもしれません）。

public class Main {

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

		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);

		Edge edges[] = new Edge[m];

		double sumOfLength = 0;

		Point points[] = new Point[n];

		//各点の座標の初期化
		for(int i = 0; i < n; i++){
			tmpArray = br.readLine().split(" ");
			int x = Integer.parseInt(tmpArray[0]);
			int y = Integer.parseInt(tmpArray[1]);

			points[i] = new Point(x, y);
		}

		//コストは点と点の間の距離
		//ここで辺の総和も求める
		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");
			int from = Integer.parseInt(tmpArray[0]) - 1;
			int to = Integer.parseInt(tmpArray[1]) - 1;
			double cost = points[from].distance(points[to]);

			edges[i] = new Edge(from,to, cost);

			sumOfLength += cost;
		}

		//辺の長さの総和から最大全域木のサイズを引いたものが答え
		System.out.printf("%.3f\n", sumOfLength - kruskal(edges, n));
	}


	static final int INF = Integer.MAX_VALUE;


	//クラスカル法
	static double kruskal(Edge[] edges, int n){
		int numOfEdge = edges.length;

		Arrays.sort(edges);

		DisjointSet set = new DisjointSet(n);

		double result = 0;

		for(int i = 0; i < numOfEdge ; i++){
			Edge tmpEdge = edges[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;
	double cost;

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

	//長い順に並ぶように
	@Override
	public int compareTo(Edge e) {
		return this.cost == e.cost ? 0 : (this.cost < e.cost ? 1 : -1);
	}
}