我们知道在构造最小生成树的时候有可能会选择不同的边，这样构造的最小生成树不相同，但是最小生成树的权是唯一的！
毫无疑问，无向图中存在相同权值的边是最小生成树不唯一的必要条件（但不是充分条件）。正因为如此，如果无向图中各边的权值都不相同，那么在用Kruskal算法构造最小生成树时，选择的方案是唯一的。
这里给出判定最小生成树唯一的算法思路：
1.对图中的每一条边，扫描其他边，如果存在相同权值的边，则对此边做标记。
2.然后使用Kruskal（或者prim）算法求出最小生成树。
3.如果这时候的最小生成树没有包含未被标记的边，即可判定最小生成树唯一。如果包含了标记的边，那么依次去掉这些边，再求最小生成树，如果求得的最小生成树的权值和原来的最小生成树的权值相同，即可判断最小生成树不唯一。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=11000; const int M=15005; int n,m,cnt; int parent[N]; int flag; struct edge { int u; int v;//顶点 int w;//权值 int equals;//是否存在与该边权值相同的其他边 int used;//在第一次求得的MST中是否包含该边。1包含，0不包含 int del;//边是否删除的标志 } edg[N]; int cmp(edge x,edge y) { return x.w<y.w; } void init() { int i; for(i=0; i<=N; i++) { parent[i]=i; } } int Find(int x) { if(parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; }//查找并返回节点x所属集合的根节点 void Union(int x,int y) { x = Find(x); y = Find(y); if(x == y) { return; } parent[y] = x; }//将两个不同集合的元素进行合并 int Kruskal() { init(); int sum=0; int num=0; for(int i=0; i<m; i++) { if(edg[i].del==1) { continue; } int u=edg[i].u; int v=edg[i].v; int w=edg[i].w; if(Find(u)!=Find(v)) { sum+=w; if(flag) { edg[i].used=1; } num++; Union(u,v); } if(num>=n-1) { break; } } return sum; } int main() { int t; int i,j; int counts1,counts2,flag2; scanf("%d",&t); while(t--) { counts1=0; scanf("%d%d",&n,&m); for(i=0; i<m; i++) { scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w); edg[i].del=0; edg[i].used=0; edg[i].equals=0;//一开始这个地方eq没有初始化，WA了好几发 } for(i=0; i<m; i++)//标记相同权值的边 { for(j=0; j<m; j++) { if(i==j) { continue; } if(edg[i].w==edg[j].w) { edg[i].equals=1; } } } sort(edg,edg+m,cmp); flag=1; counts1=Kruskal();//第1次求MST flag=0; flag2=1; for(j=0; j<m; j++) { if(edg[j].used&&edg[j].equals)//在第一次MST中包含该边，并且该边具有权值相同的边 { edg[j].del=1;//删除掉该边，进行第二次MST counts2=Kruskal();//printf("%d %d ",i,s); if(counts2==counts1) { flag2=0; printf("Not Unique! "); break; } edg[j].del=0;//恢复被删掉的边 } } if(flag2) { printf("%d ",counts1); } } return 0; }