最小生成树唯一的路径就是当前权值里，仅有一条路可以走，不存在最小权值一样的情况，如：1 2 2， 2 3 2， 1 3 2，第一次路径为1—2权值为2，但当下一次到3这个点时就存在分歧，因为1—3的权值是2，2—3的权值也是2，有两个选择。
例题： https://vjudge.net/contest/319242#problem/K
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a
subgraph of G, say T = (V’, E’), with the following properties:
1. V’ = V.
2. T is connected and acyclic.
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E).
The minimum spanning tree T = (V, E’) of G is the spanning tree that has the smallest total cost. The total cost of
T means the sum of the weights on all the edges in E’.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string ‘Not Unique!’.
Sample Input
2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2
Sample Output
3 Not Unique!
解题思路：最短路径的prime算法，求出每一次到顶点的权值，然后比较各个点到最短边的权值是否有相同的，注意：会存在至少一条边满足相同，那就是本身这条边。
程序代码：
#include<stdio.h> #include<string.h> int e[2000][2000],dis[5000],book[5000]; int inf=99999999; int main() { int i,j,k,n,m,t1,t2,t3,min,l,v,sun; int count,sum; int N,flag; scanf("%d",&N); while(N--) { flag=0; count=0; sum=sun=0; l=1; memset(dis,0,sizeof(dis)); memset(book,0,sizeof(book)); memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(j==i) e[i][j]=0; else e[i][j]=inf; for(i=1;i<=m;i++) { scanf("%d%d%d",&t1,&t2,&t3); if(e[t1][t2]>t3)//可能同样的边会出现两次，所以取较短的边 { e[t1][t2]=t3; e[t2][t1]=t3; } } for(i=1;i<=n;i++) dis[i]=e[1][i]; book[1]=1; count++; while(count<n) { min=inf; for(i=1;i<=n;i++) { if(book[i]==0&&dis[i]<min) { min=dis[i]; j=i; } } sun=0;//初始化有相同边的数目 for(v=1;v<=n;v++)//寻找n条边中已经标记的的边中是否有相同的边 if(book[v]==1&&min==e[v][j]) sun++; if(sun>1)//sun>1说明最少有一条边与当前最小值一样 break; book[j]=1; sum+=dis[j]; count++; for(k=1;k<=n;k++) if(book[k]==0&&dis[k]>e[j][k]) dis[k]=e[j][k]; } if(sun<=1) printf("%d\n",sum); else printf("Not Unique!\n"); } return 0; }
