#include <iostream>
#include <algorithm>
using namespace std;
struct road
{
	int a,b,dist;
}e[5000];
int root[105],tag[105],n,m,T,k[105],note;
int cmp(road a,road b)
{
	if(a.dist<b.dist)
		return 1;
	else
		return 0;
}
int find(int a)
{
	if(root[a]==a)return a;
	find(root[a]);
}
int kruskal()
{
	int a,b,i,s=0,count=0;
	for(i=0;i<n;i++)
		root[i]=i;
	for(i=0;i<m;i++)
	{
		if(tag[i])
			continue;
		a=find(e[i].a);
		b=find(e[i].b);
		//	printf("%d %d\n",a,b);
		if(a!=b)
		{
			s+=e[i].dist;
			root[b]=a;
			if(note==0)
				k[count]=i;
			count++;
			if(count==n-1)
				break;
		}
	}
	if(count==n-1)
		return s;
	return -1;
}
int main()
{
	int i;
	while(scanf("%d",&T)==1)
	{
		while(T--)
		{
			note=0;
			int a=0,b;
			scanf("%d%d",&n,&m);
			if(m)
			{
				for(i=0;i<m;i++)
				{
					scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].dist);
					e[i].a--;e[i].b--;
				}
				memset(tag,0,sizeof(tag));
				sort(e,e+m,cmp);
				a=kruskal();
				//	cout<<endl;
				if(a!=-1)
				{
					note=1;
					memset(tag,0,sizeof(tag));
					for(i=0;i<n-1;i++)
					{
						tag[k[i]]=1;
						b=kruskal();
						tag[k[i]]=0;
						//cout<<b<<endl;
						if(a==b)
							break;
					}
					//cout<<a<<endl;
					if(i==n-1)
						printf("%d\n",a);
					else
						printf("Not Unique!\n");
				}
				else
					printf("0\n");
			}
			else
				printf("0\n");
			
		}
	}
	return 0;
}

• Re:日，tag的数组开得太小了，搞死我了 (0) 332836708 2011-07-27 20:42:18