[BOJ/백준][Gold4] 1774 : 우주신과의 교감 (C++)

www.acmicpc.net/problem/1774  

1774번: 우주신과의 교감

 

[난이도] Gold4

[유형] MST(Kruskal)

 

[풀이]

MST를 구하는 문제이다. 이미 연결되어있는 간선들은 무조건 MST에

포함되어야 하므로 미리 union(merge) 연산으로 합쳐준 뒤에 나머지 최적의

간선들을 합쳐준다. 좌표 범위가 크므로 long long을 사용해야 한다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
int N,M,uf[1001],cnt;
double ans;
ll x[1001],y[1001];
double dist(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
 
int find(int a){
    if(uf[a]==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;
}
struct edge{
    int u,v;
    double d;
};
vector<edge> egs;
bool cmp(edge& a,edge& b){
    return a.d < b.d;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        scanf("%d%d",&x[i],&y[i]);
        uf[i]=i;
    }
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(merge(u,v)){
            cnt++;
        }
    }    
    for(int i=1;i<N;i++)
        for(int j=i+1;j<=N;j++)
            egs.push_back({i,j,dist(i,j)});
    sort(egs.begin(),egs.end(),cmp);
    for(int i=0;i<egs.size();i++){
        if(merge(egs[i].u,egs[i].v)){
            ++cnt;
            ans+=egs[i].d;
        }
        if(cnt==N-1) break;
    }
    printf("%.2f",ans);
}

 

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