[백준 4386] 별자리 만들기

분류 : 크루스칼

 

요구사항

별자리를 이은 최소 신장 트리의 크기 구하기

 

풀이

각 별자리 간의 길이를 저장해준 뒤, 최소 신장 트리를 구한다

 

#include <stdio.h>
#include <map>
#include <algorithm>
//#include "Windows.h"
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <math.h>

using namespace std;
struct go{
	double x;
	double y;
	double z;
};
int parent[100001];
vector<go> dist;
vector<go> mydist;
int n,m;
int Find(int x){
	if(parent[x]==x) return x;
	return parent[x]=Find(parent[x]);
}

void Union(int x, int y){
	x= Find(x);
	y= Find(y);
	if(x!=y) parent[x]=y;
}

bool com(go a, go b){
	if(a.z < b.z) return true;
	return false;
}
int main(){
		scanf("%d",&m);
		double sum=0;
		for(int i=1 ; i <= m ; i++) parent[i]=i;
		dist.clear();
		for(int i=0 ; i < m ; i++){
			double x, y;
			cin>>x>>y;
			dist.push_back({x,y});
		}
		int a=0;
		for(double i=0 ; i < m ; i++){
			for(double j=i+1; j <m ; j++){
				double nowx = dist[i].x;
				double nowy = dist[i].y;
				double nextx= dist[j].x;
				double nexty= dist[j].y;
				double getdist = sqrt( abs(nowx-nextx) * abs(nowx-nextx)  + abs(nowy-nexty) * abs(nowy-nexty) );
	
				mydist.push_back({i,j,getdist});
				a++;
			}

		}
		sort(mydist.begin(),mydist.end(), com);
		int cnt=0;
		for(int i=0 ; i < a ; i++){
			double x = mydist[i].x;
			double y = mydist[i].y;
			double ddist= mydist[i].z;
			if(Find(x) != Find(y)){
				Union(x,y);
				sum+=ddist;
				cnt++;
			}
			if(cnt==m-1) break;
		}
		//cout<<sum<<endl;
		printf("%.2f",sum);

}