[백준 6497] 전력난

분류 : 크루스칼

요구사항

기본적인 크루스칼 문제

 

풀이

최소 신장 트리의 합을 구하여 전체 합에서 빼준다

 

#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(){
	while(true){
		scanf("%d%d",&n,&m);
		int sum=0;
		if(n==0 && m==0) break;
		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});
			sum+=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-1) break;
		}
		//cout<<sum<<" "<<ans<<endl;
		cout<<sum-ans<<endl;


	}
}