[Algorithm] 🖧白駿1922ネットワーク接続

0、問題

道賢はコンピューターとコンピューターを接続するネットワークを構築しなければならない.しかし残念なことに、ハブがなく、コンピュータとコンピュータを直接接続する必要があります.しかし、みんなが資料を共有するために、すべてのパソコンがつながっています.(aとbの接続はaとbの経路が存在することを意味する.aとbには接続線があり、bとcには接続線があり、aとcには接続線がある.)
しかし、コンピューターに接続する費用を最小限に抑える以上、コンピューターに接続する費用のほかに、他の場所にお金を使うこともできます.これにより、各コンピュータへの接続に必要なコストが達成されると、すべてのコンピュータへの接続に必要な最低コストが出力されます.接続できないパソコンは1台もありません.
入力
第1行は、計算機数N(1≦N≦1000)を与える.
2行目は、接続可能な直線数M(1≦M≦100000)を与える.
3行目からM+2行目まで、各コンピュータをM行に接続するのに必要な費用.この費用の情報は3つの整数であり、a b cが与えられた場合、aコンピュータとbコンピュータを接続する費用はc(1≦c≦10000)であることを示す.aとbは同じかもしれません.
しゅつりょく
すべてのコンピュータを接続するために必要な最小コストを最初のローに出力します.

1.アイデア

💡 Kruskalアルゴリズム利用→MST問題
💡 始点と終点が等しい可能性のある条件のMST問題が追加されました.

2.コア解答

1)始点と終点が同じ場合はループであるため保存しない.

for(int i=0; i<m; i++) {
	String[] s = br.readLine().split(" ");
	int start = Integer.parseInt(s[0]);
	int end = Integer.parseInt(s[1]);
	int cost = Integer.parseInt(s[2]);
			
	if(start == end)
		continue;
			
	pq.add(new Edge(start, end, cost));
}

MSTのコードと同じ

3.コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.io.IOException;
public class Graph_8 {
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		parent = new int[n+1];
		for(int i=1; i<n+1; i++)
			parent[i] = i;
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		for(int i=0; i<m; i++) {
			String[] s = br.readLine().split(" ");
			int start = Integer.parseInt(s[0]);
			int end = Integer.parseInt(s[1]);
			int cost = Integer.parseInt(s[2]);
			
			if(start == end)
				continue;
			
			pq.add(new Edge(start, end, cost));
		}
		
		int ret = 0;
		while(!pq.isEmpty()) {
			Edge e = pq.poll();
			if(find(e.start) == find(e.end))
				continue;
			else {
				union(e.start, e.end);
				ret += e.cost;
			}
		}
		
		System.out.println(ret);
	}
	
	static int find(int e) {
		if(parent[e] == e) return e;
		return parent[e] = find(parent[e]);
	}
	
	static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		
		if(rootA != rootB) parent[rootB] = rootA;
	}
	
	static class Edge implements Comparable<Edge>{
		int start;
		int end;
		int cost;
		
		Edge(int start, int end, int cost) {
			this.start = start;
			this.end = end;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

}

4.結果

成功