문제 출처

1. 문제설명

• 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.
• 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.
• 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다.
• 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.
• 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
• 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.
• 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.

• 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고자 한다.

• 문제 분류
  • Graph, MST

2. 알고리즘 설계

• MST 문제로 크루스칼 알고리즘으로 해결하였다.
• 이 문제의 경우 문제를 잘 읽어서 조건을 잘 파악해야 한다.
• 우선 간선의 개수는 노드의 개수 - 1이 된다.
• 마을을 두개로 분리 할 계획이므로, 노드의 개수 - 2개의 간선을 그리디하게 연결해주면 된다.
• 그리고, 마을이 두개인 경우에는 연결할 필요가 없으므로, 이에 대한 예외처리를 해줘야 한다.
  • 마을이 두개라면 정답이 0이다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ti3 = tuple<int,int,int>;

int a, b, c, n, m, P[100'002], ans, cnt;
ti3 adj[1'000'002];

int Find(int x) { return P[x] = (x == P[x] ? x : Find(P[x])); }
bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if(x == y) return false;
	P[x] = y;
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=0; i<m; i++) {
		cin >> a >> b >> c;
		adj[i] = {c, a, b};
	}

	for(int i=1; i<=n; i++) P[i] = i;
	sort(adj, adj+m);

	for(int i=0; i<m && n>2; i++) {
		tie(c, a, b) = adj[i];
		if(Union(a, b)) {
			ans += c;
			cnt++;
		}
		if(cnt == n-2) break;
	}
	cout << ans;

	return 0;
}