[ BOJ 백준 1197번 - 최소 스패닝 트리 ] 해설 및 코드

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

목적

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하자.

 

접근법

1. 크루스칼 알고리즘의 기본 응용 문제이다. 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
const int V = 1e4, E = 1e5;
int p[V+1];
struct edge{
    int a,b,c;
    bool operator<(const edge& oth)const{
        return c<oth.c;
    }
}ed[E];
 
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);
        
    int v,e;cin>>v>>e;
    memset(p,-1,sizeof(int)*(v+1));
    f(i,0,e)cin>>ed[i].a>>ed[i].b>>ed[i].c;
    sort(ed,ed+e);
 
    int ans=0;
    f(i,0,e){
        int ra=find(ed[i].a),rb=find(ed[i].b);
        if(ra==rb)continue;
        ans+=ed[i].c;
        p[ra]=rb;
    }
    cout<<ans;
        
    return 0;
}
 

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

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