[1647] 도시 분할 계획

https://www.acmicpc.net/problem/1647

이 문제는 MST로 해결할 수 있습니다.

MST라고 생각한 이유

1. 모든 집은 전부 연결되어야 한다.

2. 필요 없는 다리는 제거한다.(유지 비용이 작은 다리만 남겨둔다.)

이 두 가지 조건을 보고 MST라고 생각했습니다.

그렇다면 한 마을을 두 마을로 어떻게 나눌까요?

진짜 간단합니다.

두 마을로 나눴을 때 한쪽 마을에 집이 한 채 이상이라면 두 마을로 나눠진 것입니다.

즉, 크루스칼을 이용하여 n - 2개의 다리만 연결하면 됩니다.

왜 n - 1이 아닌 n - 2인지 설명해드리겠습니다.

우선 마을이 하나라고 생각하고 MST를 이용해 모든 집을 연결하겠지요?

그리고 두 마을로 나눠야하는데

제가 생각했을 때 어차피 최소 비용을 유지하려면 가장 유지비가 큰 다리를 제거하면 된다는 것입니다.

그래서 n - 1개를 연결하고 그 다리 중에 가장 큰 비용의 다리 하나를 제거하면 된다는 뜻이 됩니다.

근데 크루스칼은 어차피 최소 비용을 가진 것 부터 처리하므로 애초에 마지막 다리를 설치하지도 않은 채 n - 2개의 다리만

연결한다면 문제를 해결할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
int parent[MAX_SIZE];
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
 
    if (x != y) {
        parent[x] = y;
        
        return 1;
    }
 
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) parent[i] = i;
 
    priority_queue < pair<int, pii> > pq;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        pq.push(mp(-c, mp(a, b)));
    }
 
    int sum = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt < n - 2) {
        int cost = -pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        pq.pop();
 
        if (!merge(a, b)) continue;
        
        cnt++;
        sum += cost;
    }
 
    cout << sum;
 
    return 0;
}