SDUT 2933-人活着系列之Streetlights（最小生成树Kruskal+并查集实现）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#define L long long
using namespace std;
const int INF=1<<27;
const int maxn=200010;
int m,n,v[maxn],u[maxn],w[maxn],fa[maxn],eg[maxn];
bool cmp(int x,int y)
{
	return w[x]<w[y];
}
void Make_set()
{
	for(int i=0;i<n;i++)
		fa[i]=i;
}
int Find(int x)
{
	return x==fa[x]?x:fa[x]=Find(fa[x]);
}
int Kruskal()
{
	int cnt=0,i,ans=0;
	Make_set();
	for(i=0;i<m;i++)
	  eg[i]=i;
	sort(eg,eg+m,cmp);
	for(i=0;i<m;i++)
	{
		int e=eg[i];
		int fx=Find(u[e]);
		int fy=Find(v[e]);
		if(fx!=fy)
		{
			fa[fx]=fy;
			ans+=w[e];
			cnt++;
		}
	}
    if(cnt<n-1)
		return 0;
	else
		return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n>>m)
	{
		for(int i=0;i<m;i++)
			cin>>u[i]>>v[i]>>w[i];
		int ans=Kruskal();
		if(ans)
			{
				int sum=0;
				for(int i=0;i<m;i++)
					sum+=w[i];
				cout<<sum-ans<<endl;
			}
		else
			cout<<"-1"<<endl;
	}
	return 0;
}