[BOJ/백준][Gold4] 6497: 전력난 (C++)

www.acmicpc.net/problem/6497

6497번: 전력난

 

 

[난이도] Gold4

[유형] MST (크루스칼)

 

[풀이]

Kruskal 알고리즘을 이용하여 MST를 구함 주의할점 1. TC가 여러개일 수도 있다. (입력 0 0을 기준으로 종료) 2. 절약할 수 있는 양을 구해야 하므로 전체 - MST값을 빼준다.Kruskal 알고리즘을 이용하여 MST를 구함
주의할점
1. TC가 여러개일 수도 있다. (입력 0 0을 기준으로 종료)
2. 절약할 수 있는 양을 구해야 하므로 전체 - MST값을 빼준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int mx = 2e5;
int N,M,uf[mx];
struct P{
    int a,b,c;
};
vector<P> v;
bool cmp(P& a,P& 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){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a] = b;
    return 1;
}

int main(){
    while(1){
        int t=0;
        v.clear();
        scanf("%d%d",&N,&M);
        if(N==0&&M==0) return 0;
        for(int i=0;i<M;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            t+=c;
            v.push_back({a,b,c});
        }
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<N;i++) uf[i]=i;
        int ans =0,cnt=0;
        for(int i=0;i<v.size();i++){
            if(merge(v[i].a,v[i].b)){
                ans+=v[i].c;
                if(++cnt==N-1) break;
            }
        }
        printf("%d\n",t-ans);
    }
}

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