判断最小生成树是否唯一。kruskal时记录需要的边，然后枚举删除它们，每次删除时进行kruskal，如果值未变，表明不唯一。
#include<stdio.h> #include<string.h> #include<algorithm> #include<stack> using namespace std; struct Node { int l; int r; int v; }node[10020]; int pa[2003],n; bool cmp(Node a,Node b) { return a.v<b.v; } void init() { for(int i=0;i<=n;i++) pa[i]=i; } int find(int x) { if(x!=pa[x]) pa[x]=find(pa[x]); return pa[x]; } int kruskal(Node temp) { init(); int i,j,ret=0; for(i=0;i<n;i++) { int l1,l2; if(node[i].l==temp.l&&node[i].r==temp.r) continue; l1=find(node[i].l); l2=find(node[i].r); if(l1!=l2) { ret+=node[i].v; } } return ret; } int main() { int i,j,t,m; scanf("%d",&t); while(t--) { stack<Node>s; scanf("%d%d",&n,&m); init(); for(i=0;i<m;i++) { scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].v); } sort(node,node+m,cmp); int ret=0; for(i=0;i<m;i++) { int l1,l2; l1=find(node[i].l); l2=find(node[i].r); if(l1!=l2) { pa[l1]=l2; ret+=node[i].v; s.push(node[i]); } } // printf("%d ",ret); int flag=1; while(!s.empty()) { Node temp=s.top(); s.pop(); int ans=kruskal(temp); if(ans==ret) { flag=0; break; } } if(flag) printf("%d ",ret); else printf("Not Unique! "); } }