/*
只需判断等效边和必选边的个数和n-1的关系即可
*/
#include<stdio.h>
#include<stdlib.h>
#define N 110
struct node {
int u,v,w;
}f[N*N*2];
int cmp(const void *a,const void*b) {
return (*(struct node *)a).w-(*(struct node *)b).w;
}
int pre[N];
int find(int x) {
if(x!=pre[x])
pre[x]=find(pre[x]);
return pre[x];
}
int main() {
int t,n,m,i,j,sum,ff,total;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
pre[i]=i;
for(i=0;i<m;i++)
scanf("%d%d%d",&f[i].u,&f[i].v,&f[i].w);
qsort(f,m,sizeof(f[0]),cmp);
j=0;sum=0;ff=0;total=0;
for(i=0;i<m&&ff<n-1;) {
j=i;
while(f[i].w==f[j].w&&j<m) {
int a=find(f[j].u);
int b=find(f[j].v);
if(a!=b)
sum++;
j++;
}
j=i;
while(f[i].w==f[j].w&&j<m&&ff<n-1) {
int a=find(f[j].u);
int b=find(f[j].v);
if(a!=b) {
pre[a]=b;
ff++;
// printf("%d %d\n",f[j].u,f[j].v);
total+=f[j].w;
}
j++;
}
i=j;
}
if(sum>n-1)
printf("Not Unique!\n");
else
printf("%d\n",total);
}
return 0;
}
poj 1679 判断最小生成树是否唯一,布布扣,bubuko.com
原文：http://blog.csdn.net/u011483306/article/details/38563647