[cpp 最近略忙，就不寫題意思路什麼的，直接上代碼。 [cpp] #include<stdio.h> #include<stdlib.h> struct edge { int u,v,w,flag; }p[4952]; int n,m; int f[101]; int used[101]; int cmp(const void*aa,const void*bb) { return ((struct edge*)aa)->w-((struct edge*)bb)->w; } int find(int x) { return f[x]==x?x:(f[x]=find(f[x])); } int Kruskal() { int sum=0,i,x,y,t=0; for(i=0;i<m;i++) { x=find(p[i].u); y=find(p[i].v); if(x!=y) { f[x]=y; sum+=p[i].w; used[t]=i; t++; if(t==n-1) break; } } return sum; } int reKruskal() { int sum=0,i,x,y,t=0; for(i=0;i<m;i++) { x=find(p[i].u); y=find(p[i].v); if(x!=y&&!p[i].flag) { f[x]=y; sum+=p[i].w; t++; if(t==n-1) break; } } return sum; } int main() { //freopen("12.3.4.input.txt","r",stdin); int t,i,j,ans,tans,k,pt=0; scanf("%d",&t); for(i=0;i<t;i++) { scanf("%d %d",&n,&m); for(j=1;j<=n;j++) f[j]=j; for(j=0;j<n;j++) used[j]=-1; for(j=0;j<m;j++) { scanf("%d %d %d",&p[j].u,&p[j].v,&p[j].w); p[j].flag=0; } qsort(p,m,sizeof(p[0]),cmp); ans=Kruskal(); pt=0; for(j=0;j<n-1;j++) { p[used[j]].flag=1; for(k=1;k<=n;k++) f[k]=k; tans=reKruskal(); p[used[j]].flag=0; if(ans==tans&&ans!=0) { pt=1; break; } } if(pt) printf("Not Unique!\n"); else printf("%d\n",ans); } return 0; }
