AOJ-1280, PKU-3522: Slim Span

keyword

最小全域木　BruteForce　Java

問題概要

ノード数V(<100)の無向重み付きグラフが与えられる。全ての木の中で最大重み-最小重みの最小値を求める問題。

解法

下限に対して全探索する。下限さえ決めてやれば普通に最小全域木を求めると目的関数の値が計算できる。計算量O(|E|^2)。

感想

最初は下限に関して二分探索してたけどよく考えたら単調性はなかった。

import java.util.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main {

	class UnionFind{
		int[] pars;
		UnionFind(int n){
			pars = new int[n];
			for(int i=0; i<n; i++)
				pars[i] = i;
		}
		int getRoot(int x){
			return x==pars[x]?x:(pars[x] = getRoot(pars[x]));
		}
		boolean isSame(int x, int y){
			return getRoot(x) == getRoot(y);
		}
		void merge(int x, int y){
			pars[getRoot(x)] = getRoot(y);
		}
	}

	class Edge{
		int dist, e1, e2;
		Edge(int _e1, int _e2, int _d){
			this.dist = _d;
			this.e1 = _e1;
			this.e2 = _e2;
		}
	}

	class Cmp implements Comparator<Edge>{
		public int compare(Edge a, Edge b){
			return (a.dist < b.dist)?-1:(a.dist > b.dist)?1:0;
		}
	}

	Edge[] edges;
	int N, M;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			N = in.nextInt();
			M = in.nextInt();
			if(N==0 && M==0) return ;
			edges = new Edge[M];
			for(int i=0; i<M; i++){
				edges[i] = new Edge(in.nextInt()-1, in.nextInt()-1, in.nextInt());
			}
			System.out.println(solve());
		}
	}

	int solve(){
		int ans = Integer.MAX_VALUE;
		sort(edges, new Cmp());
		for(int i=0; i<M; i++){
			int mi = edges[i].dist, ma = 0, cnt=0;
			UnionFind uf = new UnionFind(N);
			for(int j=i; j<M; j++){
				if(!uf.isSame(edges[j].e1, edges[j].e2)){
					uf.merge(edges[j].e1, edges[j].e2);
					if(++cnt == N-1){
						ma = edges[j].dist;
						break;
					}
				}
			}
			if(cnt==N-1){
				ans = min(ans, ma - mi);
			}
			else{
				break;
			}
		}
		return ans==Integer.MAX_VALUE?-1:ans;
	}

	public static void main(String args[]){
		new Main().run();
	}
}