[Algorithm] 1647: 도시 분할 계획

📦1647: 도시 분할 계획

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-20
문제 확인하기

풀이

• MST를 구현한 문제이다.
• 2개로 도시를 분리하고 길의 유지비의 최솟값을 갖는 방법은 가장 유지비가 높은 도시를 떼어내어 분리하는 것이다.
• 연결되어있지 않은 경우 연결시키고 유지비용을 더해준다.
• 가장 마지막 더해주는 값을 제외한다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
int N, M, res=0, last;
int parent[100001];
vector<pair<int, pair<int, int>>> edge;
 
void Input(){
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        parent[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());
}
 
int Find(int x){
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x != y){
        parent[y] = x;
    }
}
 
int sameParent(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x == y) return 1;
    return 0;
}
 
void Solution(){
    for(int i=0; i<edge.size(); i++){
        if(sameParent(edge[i].second.first, edge[i].second.second) == 0){
            Union(edge[i].second.first, edge[i].second.second);
            last = edge[i].first;
            res += last;
        }
    }
    cout << res - last << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    Input();
    Solution();
 
    return 0;
}