[ BOJ 백준 6497번 - 전력난 ] 해설 및 코드

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

목적

임의의 두 집 사이에 불이 켜져 있는 길이 있어야 할 때, 필요한 길만 남겨 절약할 수 있는 최대 액수를 구하자.

 

접근법

1. MST를 구하는 문제이며, 크루스칼 알고리즘을 적용하며 해결하자.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
const int N = 2e5;
int p[N];
struct edge{
    int a,b,c;
    bool operator<(const edge& oth)const{
        return c<oth.c;
    }
}ed[N];
 
int find(int x){
    return p[x]<0?x:p[x]=find(p[x]);
}
        
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while(true){
        int m,n,ans=0;
        cin>>m>>n;
        if(!m&&!n)break;
        f(i,0,n)cin>>ed[i].a>>ed[i].b>>ed[i].c,ans+=ed[i].c;
        sort(ed,ed+n);
        memset(p,-1,4*m);
        f(i,0,n){
            int ra=find(ed[i].a),rb=find(ed[i].b);
            if(ra==rb)continue;
            p[ra]=rb;
            ans-=ed[i].c;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.