#include <cstdio>
#include <cstdlib>
#include <cstring>
#define N 101
using namespace std;
int n,e,father[N];
struct node {
	int u,v,c;
	node(){}
	node(int u,int v,double c):u(u),v(v),c(c){}
}p[N*N];

void addnode(int u,int v,int c){
	p[e++]=node(u,v,c);
} 

int cmp(const void *a,const void * b){
	node *aa=(node *)a;
	node *bb=(node *)b;
	return aa->c - bb->c; 
}

int find(int x){
	if(x!=father[x])
		father[x]=find(father[x]);
	return father[x];
}

void clear(){
	for(int i=0;i<=n;i++)
		father[i]=i;
}

int kruskal(int n){
	clear();
	int m=0, ans=0;
	for(int i=0;i<e;i++){
		int u=find(p[i].u);
		int v=find(p[i].v);
		if(u==v) continue;
		for(int j=i+1;j<e;j++){
			if(p[j].c!=p[i].c) break;
			//printf("%d %d\n",)
			if(find(p[j].u)==u&&find(p[j].v)==v){
				//printf("sdya");
				return -1;
			}
		}
		m++;
		ans+=p[i].c;
		father[v]=u;
		if(m==n-1)
			break;
	}
	return ans;
}

int main(){
	int t,l,a,b,c;
	scanf("%d",&t);
	while(t--){
		e=0;
		scanf("%d%d",&n,&l);
		for(int i=1;i<=l;i++){
			scanf("%d%d%d",&a,&b,&c);
			if(a<b) addnode(a,b,c);
			else addnode(b,a,c);
		}
		qsort(p,e,sizeof(p[1]),cmp);
		int ans=kruskal(n);
		if(ans==-1) printf("Not Unique!\n");
		else printf("%d\n",ans);
	}
	return 0;
}

• Re:水题 1A 附代码 (1445) 70 2015-04-04 23:27:43