[백준] 1647 : 도시 분할 계획

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

1647번: 도시 분할 계획

---

• 문제를 요약하자면, 어떤 그래프를 둘로 쪼개고 싶은데, 갈라진 그래프 속에서도 최소 스패닝 트리를 만들고 싶다는 것이다.
• 각 그래프의 최소 스패닝 트리를 만든다는 것은, 전체 그래프의 MST 를 둘로 쪼개는 것과 같다.
• 따라서 전체 그래프의 MST 가중치를 구한 뒤, 그를 구성하는 에지들 중 가장 큰 비용을 기준으로 트리를 잘라주면 된다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, M, A, B, C;
int parent[100001];

int find_(int x)
{
    if(parent[x] == 0) return x;
    parent[x] = find_(parent[x]);
    return parent[x];
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;

    for(int i = 0 ; i < M ; i++)
    {
        cin >> A >> B >> C;
        pq.push({C, {A,B}});
    }

    int maxi = 0;
    int total = 0;

    while(pq.size())
    {
        int dist = pq.top().first;
        int x = find_(pq.top().second.first);   // 각 노드의 루트값을 찾아서
        int y = find_(pq.top().second.second);
        pq.pop();
        if(x != y)                              // 다른 집단에 속할(순환이 일어나지 않을) 경우에만
        {
            parent[x] = y;                      // 두 집단 유니온
            total += dist;                      // MST 에 포함시켜줌
            if(dist > maxi) maxi = dist;        // MST 를 둘로 나눌 기준 에지 찾기
        }
    }

    cout << total - maxi << endl;
}