I♥TLE

Java、オンラインジャッジなど

2377-Bad Cowtractors

問題(外部リンク)

2377 -- Bad Cowtractors

実装の概要

今回は普段とは異なり「なるべくコストの大きい」全域木を作ることが目標です。
ただ、既にプリム法やクラスカル法を実装したことがあれば条件式を逆にすれば良いので既存のコードを再利用することができます。
下記の実装ではクラスカル法を採用しています。

気をつけなければならないのは、今回は入力されたグラフが連結とは限らないということです。
連結かどうかの判定にはダイクストラ法を使います。ある特定の点から任意の点までの距離が求められれば連結だと分かるので、ワーシャルフロイド法の必要はありません。

ダイクストラ法もクラスカル法も計算量はO(M \log N)なので、両方実行しても十分間に合います。

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];

		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;
			int cost = Integer.parseInt(tmpArray[2]);

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

		int distFrom0[] = dijkstra(edges, 0, n);

		//特定の地点から全ての地点に到達可能かチェック
		for(int i = 0; i < n; i++){
			if(distFrom0[i] == INF){
				System.out.println(-1);
				return;
			}
		}

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


	static final int INF = Integer.MAX_VALUE;

	//ダイクストラ法
	static int[] dijkstra(Edge[] edgesArray, int s, int n){

		//配列の形で受け取ったものを
		//ArrayListに作り変える
		@SuppressWarnings("unchecked")
		ArrayList<Edge> edges[] = new ArrayList[n];

		for(int i = 0; i < n; i++){
			if(edges[i] == null){
				edges[i] = new ArrayList<Edge>();
			}
		}

		for(int i = 0; i < edgesArray.length; i++){
			Edge tmp = edgesArray[i];
			edges[tmp.from].add(tmp);
		}

		PriorityQueue<Distance> que = new PriorityQueue<Distance>();
		int[] dist = new int[n];

		Arrays.fill(dist, INF);
		dist[s] = 0;
		que.add(new Distance(0, s));

		while(!que.isEmpty()){
			Distance tmpDist = que.poll();
			int tmpV = tmpDist.id;

			if(dist[tmpV] < tmpDist.dist){
				continue;
			}
			for(int i = 0; i < edges[tmpV].size() ; i++){
				Edge e = (Edge) edges[tmpV].get(i);
				if(dist[e.to] > dist[tmpV] + e.cost){
					dist[e.to] = dist[tmpV] + e.cost;
					que.add(new Distance(dist[e.to], e.to));
				}
			}
		}

		return dist;
	}

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

		Arrays.sort(edges);

		DisjointSet set = new DisjointSet(n);

		long 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 Distance implements Comparable<Distance>{
	int dist;
	int id;

	Distance(int dist, int id){
		this.dist = dist;
		this.id = id;
	}

	@Override
	public int compareTo(Distance d) {
		return this.dist - d.dist;
	}
}

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;
		return e.cost - this.cost;
	}
}