POJ1679The Unique MST （最小生成树之Prim ）(有点坑人)
Problem Description
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!题目意思是：在给定的数据中，找到一棵最小生成树，如果这棵最小生成树是唯一的那么就输出最小生成树上权的和，不是唯一的就输出Not Unique!解法：先建立一棵最小生成树，然后找一条边不在最小生成树上，把这条边作为起始边开始建最小生成树，如果找到一棵最小生成树与第一次建的最小生成树权值相等，那么就不用再找了，直接输出Not Unique!
#include<stdio.h>
#include<string.h>
typedef struct sn {
int v;//用于记录与当前点相连的点
int dist;//权值 }Node;
Node node[105];
int n,s[105],vist[105][105],map[105][105],INF=1000000;
void set_first(int n)//初始化
{ for(int i=1;i<=n;i++)
{ s[i]=0; node[i].dist=INF;
for(int j=i+1;j<=n;j++) map[i][j]=map[j][i]=INF;
} memset(vist,0,sizeof(vist));
} int Prim(int m,int sum,int flog) { int tm=m,min,i;
s[m]=1;
if(flog==0)i=2;//如果flog=0就是s集合己有1个点，否则有2个点 else i=3;
for( ;i<=n;i++) { min=INF;
for(int j=1;
j<=n;j++) if(s[j]==0) {
if(node[j].dist>map[tm][j])//更新权值，并且更新与j相连的点tm { node[j].dist=map[tm][j];
if(flog==0) node[j].v=tm;
} if(min>node[j].dist)//找到最小的权值并记录点位置 { min=node[j].dist; m=j;
} } sum+=min; tm=m; s[m]=1;
if(flog==0)
vist[node[m].v][m]=vist[m][node[m].v]=1;
//为1时边在最小生成树上，否则不在树上 } return sum;
} int main() { int t,a,b,w,m,sum1,sum2;
scanf("%d",&t);
while(t--) { scanf("%d%d",&n,&m);
set_first(n);//初始化
while(m--) { scanf("%d%d%d",&a,&b,&w);
if(map[a][b]>w)//判断重边
map[a][b]=map[b][a]=w; } sum1=Prim(1,0,0);
int flog=0;
for(int i=1;i<n;i++)//找一条不在最小生成树上的边，然后从这条边开始建树 { for(int j=i+1;j<=n;j++)//从i+1开始为了不重复，因为如：1到2和2到1是一样的
if(vist[i][j]==0&&map[i][j]!=INF)
{ for(int e=1;e<=n;e++)//初始化 {
s[e]=0; node[e].dist=INF;
}
s[i]=1;//加入第一个点 for(int e=1;e<=n;e++)//更新与第一个点相关的点 { node[e].dist=map[i][e];
} sum2=Prim(j,node[j].dist,1);//从点j开始找 if(sum2==sum1){flog=1;break;}//找到有多种可能，跳出
} if(flog)break; } if(flog==0)
printf("%d\n",sum1);
else printf("Not Unique!\n"); } }
补充：软件开发 , C++ ,
