C++ 백준 1647 (도시 분할 계획)

백준 1647 (도시 분할 계획)

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

1647번: 도시 분할 계획

---

설명

---

이 문제는 MST를 찾는 문제이다. 

 

MST를 찾기 위해 크루스칼 알고리즘을 사용해야하는데 이에 대한 자세한 설명은 여기(링크)에 있다.

 

연결되어있는 여러 도시를 가장 작은 MST 두개의 그룹으로 나누는 것이 문제의 목표이다.

때문에 주어진 그래프의 MST로 찾은 후에 찾은 MST중 가중치가 가장 큰 엣지만 제거한다면 문제를 쉽게 해결할 수 있다!

 

구현

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int p[100001];
int n;
long long ans=0;
int M = 0;
vector <pair<int, pair<int, int>>> edge;

int find(int a){
    if(p[a]==a) return a;
    return p[a]=find(p[a]);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int m;
    int count=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        edge.push_back({c,{a,b}});
    }
    sort(edge.begin(),edge.end());
    for(int i=0;i<edge.size();i++){
        if(count == n-1) break; // 채택한 엣지의 개수가 V-1개면 이미 MST가 완성된 것이다.
        pair<int, pair<int ,int >> temp = edge[i];
        int tmp1= find(temp.second.first);
        int tmp2 = find(temp.second.second);
        if(tmp1 == tmp2) continue;
        p[tmp2] = tmp1; //merge와 같다.
        ans+=temp.first;
        M = max(M, temp.first); // 채택된 엣지중 가장 큰 엣지의 가중치를 저장
    }
    cout<<ans-M; // 만든 MST의 엣지 합에서 가중치가 가장 큰 엣지의 가중치를 뺀다. (두개의 그룹으로 나눔) 
    return 0;
}