poj1861.cpp

最小生成树的几种算法的实现

#include <cstdio>
#include <memory>
#include <algorithm>
using namespace std;

int n,m;
int p[1010],rank[1010];
bool used[15010];

void makeset()
{
	int i;
	for(i=0;i<1010;++i)
	{
		p[i]=i;
		rank[i]=0;
	}
}

int findset(int x)
{
	int i,px=x;
	while(px!=p[px]) px=p[px];
	while(x!=px)
	{
		i=p[x];
		p[x]=px;
		x=i;
	}
	return px;
}

void unionset(int x,int y)
{
	x=findset(x);
	y=findset(y);
	if(rank[x]>rank[y]) p[y]=x;
	else
	{
		p[x]=y;
		if(rank[x]==rank[y])
			rank[y]++;
	}
}

struct edge
{
	int x;
	int y;
	int len;
};

edge e[15010];

bool com(edge a,edge b)
{
	return a.len<b.len;
}

int main()
{
	int tol,i,ans;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(used,0,sizeof(used));
		makeset();
		ans=tol=0;
		for(i=0;i<m;++i)
			scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].len);
		sort(e,e+m,com);
		for(i=0;i<m;++i)
		{
			if(findset(e[i].x)!=findset(e[i].y))
			{
				unionset(e[i].x,e[i].y);
				if(e[i].len>ans) ans=e[i].len;
				tol++;
				used[i]=1;
			}
		}
		printf("%d\n%d\n",ans,tol);
		for(i=0;i<m;++i)
			if(used[i]) printf("%d %d\n",e[i].x,e[i].y);
	}
	return 0;
}