poj 2377

题意:Bessie为了报复雇主,决定将雇主让他做的工作竟可能的做得很糟糕,他的想法如下:
                1>使整个网络的花费竟可能的最大;   
                2>保证建成的网络是连通图,即任意两定点之间都存在路径;    
                3>建成的网络没有环(即回路)存在.
    现在要求建成该网络的最大花费,如果建成的网络不是连通图,则输出"-1".
    最大生成树,用Kruskal算法求解,只需将边按权值降序排序,然后就是和最小生成树中的算法一样.而如果使用Prim算法则要考虑重边的情况,但用Kruskal算法则不需要考虑重边,因为我们已经将边进行了排序,当一条边加入的时候,不可能再加入重边.

使用Kruskal算法，加以考虑使用并查集的这种数据结构，通过这道题目，即回忆了并查集，有进一步复习了Prime算法。代码如下：

#include <iostream>
#include <algorithm>
using namespace std;


const int Max=20005;

struct Edge 
{
	int u,v,w;
}e[Max];

int p[10005];
int r[10005];

bool cmp(const Edge &a,const Edge &b)
{
	return a.w>b.w;
}

void inital(int x)
{
	p[x]=x;
	r[x]=1;
}
int find(int x)
{
	if (x!=p[x])
		p[x]=find(p[x]);
	return p[x];
}

void Union(int x,int y)
{
	if (r[x]<r[y])
	{
		p[x]=y;
		r[y]+=r[x];
	}
	else if(r[x]>r[y])
	{
		p[y]=x;
		r[x]+=r[y];
	}
	else 
	{
		r[y]++;
		p[y]=x;
	}
}

int main()
{
	int i,n,m;
	while (cin>>n>>m&&n&&m)
	{
		for (i=0;i<n;i++)
			inital(i);
		for (i=0;i<m;i++)
			cin>>e[i].u>>e[i].v>>e[i].w;
		sort(e,e+m,cmp);
		int px,py;
		int num,ans;
		num=ans=0;
		for (i=0;i<m;i++)
		{
			px=find(e[i].u);
			py=find(e[i].v);
			if (px!=py)
			{
				Union(px,py);
				ans+=e[i].w;
				num++;
			}
		}
		if(num==n-1)
			cout<<ans<<endl;
		else
			cout<<-1<<endl;
	}
	return 0;

}