CSES 4. Road Reparation (1675)

출처: https://cses.fi/problemset/task/1675

---

문제 설명

There are n cities and mm roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

입력 

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two cities.

출력

Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".

입력 예

5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4

출력 예

14

제약조건

1 <= n <= 1e5

1<= m <= 2*1e5

1 <= a, b <= n

1 <= c <= 1e9

---

문제 풀이

도시들을 정점으로하고 연결하는 도로들을 간선으로 하는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 

간선의 비용을 기준으로 작은 것부터 도시들을 계속해서 연결해 나간다. 도시 하나를 연결할때 연결된 도시수를 기록한다. 모든 도시가 연결된다면 필요한 최소 간선의 수는 도시의 수보다 1 작은 값이 되야 한다. 이 값보다 크다면, 연결할 수 없는 도시가 존재하므로 "IMPOSSIBLE"을 출력하고, 연결되면 연결하면서 기록한 비용을 출력한다.

프로그램 내용

for(int id=0; id < tE; ++id)
{
	int a, b, c;
	cin >> a >> b >> c;
	vt.push_back({c, a, b});
}        
...
long sum = 0;
int cnt = tN;
for(int id=0; id < tE; ++id)
{
	int a, b, c;
	tie(c, a, b) = vt[id];
	if(merge(a, b))	/// union
	{
		sum += c;
		cnt--;
	}
}
...

 

 Graph Algorithms ( link )