[백준 1647] 도시 분할 계획

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

using namespace std;
struct go{
	int x;
	int y;
	int z;
};
int parent[200200];
vector<go> dist;
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%d",&n,&m);
		int sum=0;
		for(int i=0 ; i < n ; i++) parent[i]=i;
		dist.clear();
		for(int i=0 ; i < m ; i++){
			int x, y, z;
			scanf("%d%d%d",&x,&y,&z);
			dist.push_back({x,y,z});
			dist.push_back({y,x,z});
		}
		sort(dist.begin(),dist.end(),com);
		int cnt=0;
		int now=0;
		int ans=0;
		int distsize=dist.size();
		while(now != distsize){
		//	cout<<now<<endl;
			int nownode = dist[now].x;
			int nextnode = dist[now].y;
			int nowdist= dist[now].z;
			now++;
			if(Find(nownode) != Find(nextnode)){
				Union(nownode, nextnode);
				ans+=nowdist;
				cnt++;
			}
			if(cnt==n-2) break;
		}
		//cout<<sum<<" "<<ans<<endl;
		cout<<ans<<endl;

}

분류 : 크루스칼

 

요구사항

기본적인 크루스칼 문제이다

 

풀이

n-2개 크기의 최소 신장 트리를 구한다