AOJ2224 Save your cat

問題リンク Save your cat

• 概要

N本の柱が平面上に立っている。更に、柱を端点とするM個の壁がある。
壁で囲まれている内部には必ず猫がいて、壁を壊すことで猫を外に逃がしたい。
壁を壊すには、壁の長さだけコストがかかる。
猫を全て逃がすために必要な最小コストを求めよ。
以下のことが保証されている。
2 <= N <= 10000
1 <= M
-10000 <= x, y <= 10000
同じ場所に柱が2本以上あることはない
壁の途中に別の柱があることはない
壁と壁は交差していない
壁は一部分だけを壊すことはできない

• 解法

柱を頂点、壁を辺とするグラフとして考えると、閉路になっている部分が壁で囲まれている部分だと考えることができます。グラフから閉路が無くなれば、全ての猫を逃がしたことになります。よって求めるのは、辺集合M上の全域木となります。Mのうち全域木に採用されなかった辺が壊すべき壁に相当します。
Mの全ての壁のコストをsumとし、クラスカル法で全域木を作ります。コストが小さい壁を全域木に含めたくないので、コストが大きい順に全域木を作っていきます。得られた全域木のコストの和をresとすると、sum-resが答えになります。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Save your cat
public class AOJ2224 {
	
	class UnionFind {
		final int[] tree;
		int num;
		public UnionFind(int n) {
			this.tree = new int[n];
			Arrays.fill(tree, -1);
			num=n;
		}
		void union(int x, int y) {
			x = root(x);
			y = root(y);
			if(x != y) {
				if(tree[x] < tree[y]) {
					x ^= y; y ^= x; x^= y;
				}
				tree[x] += tree[y];
				tree[y] = x;
				num--;
			}
		}
		boolean find(int x, int y) {
			return root(x) == root(y);
		}
		int root(int x) {
			return tree[x] < 0 ? x : (tree[x] = root(tree[x]));
		}
		int size(int x) {
			return -tree[root(x)];
		}
		int getNum() {
			return num;
		}
	}
	
	class E implements Comparable<E>{
		int s, t;
		double d;
		public E(int s, int t, double d) {
			this.s = s;
			this.t = t;
			this.d = d;
		}
		public int compareTo(E o) {
			return (int)Math.signum(o.d-d);
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
		int[] x = new int[n+1], y = new int[n+1];
		for(int i=1;i<=n;i++){
			x[i] = sc.nextInt(); y[i] = sc.nextInt();
		}
		E[] es = new E[m];
		double sum = 0;
		for(int i=0;i<m;i++){
			int s = sc.nextInt(), t = sc.nextInt();
			double d = Math.hypot(x[s]-x[t], y[s]-y[t]);
			sum+=d;
			es[i] = new E(s, t, d);
		}
		Arrays.sort(es);
		UnionFind u = new UnionFind(n+1);
		double res = 0;
		for(E e:es){
			if(u.find(e.s, e.t))continue;
			res+=e.d;
			u.union(e.s, e.t);
		}
		System.out.printf("%.8f\n", sum-res);
	}
	
	public static void main(String[] args) {
		new AOJ2224().run();
	}
}