http://poj.org/problem?id=1679
#include<iostream> #include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node{ int u,v,w; }e[10004]; int f[110]; vector<int>vis; bool cmp(node p,node q){ return p.w<q.w; } int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } int main(){ int t; scanf("%d",&t); while(t--){ int n,m,ans=0; vis.clear(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); e[i].u=u; e[i].v=v; e[i].w=w; } sort(e+1,e+1+m,cmp); for(int i=0;i<=n;i++) f[i]=i; for(int j=0,i=1;i<=m;i++){ int u=e[i].u,v=e[i].v; int a=find(u),b=find(v); if(a!=b){ f[a]=b; j++; ans+=e[i].w; vis.push_back(i); } if(j==n-1) break; } int flag=0; for(int k=0;k<vis.size();k++){ int sign=vis[k]; int ans1=0; for(int i=0;i<=n;i++) f[i]=i; int j=0; for(int i=1;i<=m;i++){ if(i!=sign){ int u=e[i].u,v=e[i].v; int a=find(u),b=find(v); if(a!=b){ f[a]=b; ans1+=e[i].w; j++; } if(j==n-1) break; } } if(j==n-1){ if(ans1==ans){ flag=1; break; } } } if(flag) puts("Not Unique!"); else printf("%d\n",ans); } return 0; }View Code