LightOJ - 1123-Trail Maintenance （最小生成樹+克魯斯卡爾算法）

原題位址：點選打開連結

注意要删除不需要的邊，否則會逾時。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct Edge
{
	int u;
	int v;
	int cost;
}edge[6010],e[6010];
int p[210];
int k=0,n;
int cnt;
int comp(Edge e1,Edge e2)
{
	return e1.cost<e2.cost;
}
int find(int x)         
{
	if(p[x]!=x)
	{
		p[x]=find(p[x]);
	}
	return p[x];
}
bool bin(int x,int 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=1;i<=n;i++)
	{
		if(p[i]==i)
			count++;
	}
	if(count>1)
		return false;
	return true;
}
int min_tree()
{
	int i,res=0,size,count=0;
	for(i=1;i<=n;i++)
		p[i]=i;
	size=cnt;
	sort(edge,edge+cnt,comp);
	for(i=0;i<size;i++)
	{
		if(bin(edge[i].u,edge[i].v))
		{
			res+=edge[i].cost;
			count++;
		}
		else
		{
			edge[i]=edge[cnt-1];
			cnt--;
		}
	}
	if(count==n-1)
		return res;
	 return -1;
}
int main()
{
	int t,u,i,v,cost,m,k=0;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		printf("Case %d:\n",++k);
		cnt=0;
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&cost);
			edge[cnt].u=u;
			edge[cnt].v=v;
			edge[cnt++].cost=cost;
			int res=min_tree();
			printf("%d\n",res);
		}
		
	}
	return 0;
} 
/*


1
4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2

*/