[BOJ/백준][Gold4] 1647 : 도시 분할 계획(C++)

www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

 

[난이도] Gold4

[유형] 최소 스패닝 트리 (크루스칼)

 

[풀이]

크루스칼 알고리즘을 이용해 MST를 구하고 그중 가장 큰 edge를 제거하면 cost를 가장 작게하면서 마을을 두개로 나눌 수 있다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct eg{
    int c,a,b;
};
vector<eg> v;
int N,M,uf[100001],cnt,ans;
bool cmp(eg& a,eg& b){
    return a.c < b.c;
}
int find(int a){
    if(a==uf[a]) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    int pa = find(a);
    int pb = find(b);
    if(pa==pb) return 0;
    uf[pa] = find(pb);
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    v.resize(M);
    for(int i=0;i<M;i++){
        scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=1;i<=N;i++) uf[i] = i;
    for(int i=0;;i++){
        if(merge(v[i].a,v[i].b)){
            if(++cnt==N-1) break;
            ans+=v[i].c;
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1647.cpp