๋๋ฌผ์์์ ๋ง ํ์ถํ ์์ญ์ด ํ ๋ง๋ฆฌ๊ฐ ์ธ์๊ตฌ๊ฒฝ์ ํ๊ณ ์๋ค. ๊ทธ๋ฌ๋ค๊ฐ ํํ๋ก์ด ๋ง์์ ๊ฐ๊ฒ ๋์๋๋ฐ, ๊ทธ๊ณณ์์๋ ์ ์ ์๋ ์ผ์ด ๋ฒ์ด์ง๊ณ ์์๋ค.
๋ง์์ N๊ฐ์ ์ง๊ณผ ๊ทธ ์ง๋ค์ ์ฐ๊ฒฐํ๋ M๊ฐ์ ๊ธธ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ธธ์ ์ด๋ ๋ฐฉํฅ์ผ๋ก๋ ์ง ๋ค๋ ์ ์๋ ํธ๋ฆฌํ ๊ธธ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ๊ธธ๋ง๋ค ๊ธธ์ ์ ์งํ๋๋ฐ ๋๋ ์ ์ง๋น๊ฐ ์๋ค.
๋ง์์ ์ด์ฅ์ ๋ง์์ ๋ ๊ฐ์ ๋ถ๋ฆฌ๋ ๋ง์๋ก ๋ถํ ํ ๊ณํ์ ๊ฐ์ง๊ณ ์๋ค. ๋ง์์ด ๋๋ฌด ์ปค์ ํผ์์๋ ๊ด๋ฆฌํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค. ๋ง์์ ๋ถํ ํ ๋๋ ๊ฐ ๋ถ๋ฆฌ๋ ๋ง์ ์์ ์ง๋ค์ด ์๋ก ์ฐ๊ฒฐ๋๋๋ก ๋ถํ ํด์ผ ํ๋ค. ๊ฐ ๋ถ๋ฆฌ๋ ๋ง์ ์์ ์๋ ์์์ ๋ ์ง ์ฌ์ด์ ๊ฒฝ๋ก๊ฐ ํญ์ ์กด์ฌํด์ผ ํ๋ค๋ ๋ป์ด๋ค. ๋ง์์๋ ์ง์ด ํ๋ ์ด์ ์์ด์ผ ํ๋ค.
๊ทธ๋ ๊ฒ ๋ง์์ ์ด์ฅ์ ๊ณํ์ ์ธ์ฐ๋ค๊ฐ ๋ง์ ์์ ๊ธธ์ด ๋๋ฌด ๋ง๋ค๋ ์๊ฐ์ ํ๊ฒ ๋์๋ค. ์ผ๋จ ๋ถ๋ฆฌ๋ ๋ ๋ง์ ์ฌ์ด์ ์๋ ๊ธธ๋ค์ ํ์๊ฐ ์์ผ๋ฏ๋ก ์์จ ์ ์๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ๋ถ๋ฆฌ๋ ๋ง์ ์์์๋ ์์์ ๋ ์ง ์ฌ์ด์ ๊ฒฝ๋ก๊ฐ ํญ์ ์กด์ฌํ๊ฒ ํ๋ฉด์ ๊ธธ์ ๋ ์์จ ์ ์๋ค. ๋ง์์ ์ด์ฅ์ ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋๋ก ๊ธธ๋ค์ ๋ชจ๋ ์์ ๊ณ ๋๋จธ์ง ๊ธธ์ ์ ์ง๋น์ ํฉ์ ์ต์๋ก ํ๊ณ ์ถ๋ค. ์ด๊ฒ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ง์ ๊ฐ์N, ๊ธธ์ ๊ฐ์M์ด ์ฃผ์ด์ง๋ค. N์ 2์ด์ 100,000์ดํ์ธ ์ ์์ด๊ณ , M์ 1์ด์ 1,000,000์ดํ์ธ ์ ์์ด๋ค. ๊ทธ ๋ค์ ์ค๋ถํฐ M์ค์ ๊ฑธ์ณ ๊ธธ์ ์ ๋ณด๊ฐ A B C ์ธ ๊ฐ์ ์ ์๋ก ์ฃผ์ด์ง๋๋ฐ A๋ฒ ์ง๊ณผ B๋ฒ ์ง์ ์ฐ๊ฒฐํ๋ ๊ธธ์ ์ ์ง๋น๊ฐ C (1 โค C โค 1,000)๋ผ๋ ๋ป์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์์ ๊ณ ๋จ์ ๊ธธ ์ ์ง๋น์ ํฉ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
๐กMST ๊ตฌํ๋ ๋ฐฉ์์ด๋ ๊ฐ์
๐ก๋ชจ๋ ์ ์ ์ด ์ด์ด์ง ์คํจ๋ ํธ๋ฆฌ์์ ๊ฐ์ฅ ํฐ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง ํ ๊ฐ์ ์ ๋์ผ๋ฉด ๋์๊ฐ ๋ถํ ๋จ
1) ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก MST ๊ตฌํ๊ธฐ
while(!pq.isEmpty()) {
Edge e = pq.poll();
if(find(e.start) == find(e.end))
continue;
else {
union(e.start, e.end);
count += e.cost;
}
}
...
static int find(int e){
...
}
...
static int union(int a, int b){
...
}
...
2) ๊ทธ ์ค ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ํฐ ๊ฐ์ ๋์ด๋ด๊ธฐ
...
max = Math.max(max, e.cost);
...
System.out.pritnln(count-max);
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.io.IOException;
public class Graph_5 {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int M = Integer.parseInt(s[1]);
int count = 0;
int max = -1;
parent = new int[N+1];
PriorityQueue<Edge> pq = new PriorityQueue<>();
for(int i=1; i<N+1; i++)
parent[i] = i;
for(int i=0; i<M; i++) {
s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
int cost = Integer.parseInt(s[2]);
pq.add(new Edge(start,end,cost));
}
while(!pq.isEmpty()) {
Edge e = pq.poll();
if(find(e.start) == find(e.end))
continue;
else {
union(e.start, e.end);
count += e.cost;
max = Math.max(max, e.cost);
}
}
System.out.println(count-max);
}
static int find(int e) {
if(e == parent[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;
}
}
}
์ฑ๊ณตโจ