lightoj-1029-Civil and Evil Engineer(最小生成樹+克魯斯卡爾算法)

原題位址：點選打開連結

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct Edge
{
	int u;
	int v;
	int cost;
}edge[12010];
int p[110];
int k=0,n;
int comp1(Edge e1,Edge e2)
{
	return e1.cost<e2.cost;
}
int comp2(Edge e1,Edge e2)
{
	return e1.cost>e2.cost;
}
int find(int x)          //找到x所屬集合 
{
	if(p[x]!=x)
	{
		p[x]=find(p[x]);
	}
	return p[x];
}
bool bin(int x,int y)   //将x y添加至一個集合中 
{
	int g,h;
	g=find(x);
	h=find(y);
	if(g!=h)
	{
		p[g]=h;
		return true;
	}
	return false;
}
bool judge()
{
	int count=0;
	for(int i=0;i<=n;i++)
	{
		if(p[i]==i)
			count++;
	}
	if(count>1)
		return false;
	return true;
}
int main()
{
	int t,u,i,v,cost,m,res,k=0;
	scanf("%d",&t);
	while(t--)
	{
		m=0;
		res=0;
		scanf("%d",&n);
		while(scanf("%d%d%d",&u,&v,&cost)&&(u||v||cost))
		{
			edge[m].u=u;
			edge[m].v=v;
			edge[m++].cost=cost;
		}
		for(i=0;i<=n;i++)
			p[i]=i;
		sort(edge,edge+m,comp1);
		for(i=0;i<m;i++)
		{
			if(bin(edge[i].u,edge[i].v))
			{
				res+=edge[i].cost;
				if(judge())
					break;
			}		
		}
		for(i=0;i<=n;i++)
		p[i]=i;
		sort(edge,edge+m,comp2);
		for(i=0;i<m;i++)
		{
			if(bin(edge[i].u,edge[i].v))
			{
				res+=edge[i].cost;
				if(judge())
					break;
			}		
		}
		if(res%2==0)
			printf("Case %d: %d\n",++k,res/2);
		else
			printf("Case %d: %d/2\n",++k,res);
	}
	return 0;
} 
/*


3
1
0 1 10
0 1 20
0 0 0
3
0 1 99
0 2 10
1 2 30
2 3 30
0 0 0
2
0 1 10
0 2 5
0 0 0
*/