1647번 도시 분할 계획

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

1647번: 도시 분할 계획

 

마을을 두개로 분할해야하며 각 마을은 서로 길이 이어져야한다.
여기서 중요한 점은 마을에 집이 하나 이상 있어야 한다는 것이다. 이게 뭘 뜻하냐면 예를 들어 길을 연결하는 비용을 오름차순으로 연결했다고 치자 그러면 마지막 길 연결 비용이 가장 클 것이다. 따라서 마지막 길만 다른 마을로 보내면 그 길을 연결해도 되지 않으므로 마을 연결 비용이 최솟값이 된다. 만약 마지막 길로 보낸 마을에 또 다른 집을 보낸다면 그 길을 연결할 비용이 들기 때문에 최솟값이 되지 않는다.

 

#include <bits/stdc++.h>
#define l long long
#define INF 2e9
#define p pair<int,int>
#define vc vector<int>
using namespace std;

int root[100001];

int Find(int x){
    if(root[x] == x) return x;
    else return root[x] = Find(root[x]);
}

void Union(int x,int y){
    x = Find(x), y = Find(y);

    if(x < y) root[y] = x;
    else root[x] = y;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int V,E,a,b,c,cnt = 0,ans = 0;

    cin >> V >> E;

    for(int i=1;i<=V;i++)
        root[i] = i;

    tuple<int,int,int> node[E];

    for(int i=0;i<E;i++){
        cin >> a >> b >> c;

        node[i] = {c,a,b};
    }

    sort(node,node + E);

    for(int i=0;i<E;i++){
        tie(c,a,b) = node[i];

        if(Find(a) == Find(b)) continue;

        Union(a,b);
        ans += c;
        cnt++;
        if(cnt == V-2) break;
    }
    cout << ans;
}