题目链接：http://poj.org/problem?id=1679
判断最小生成数是否唯一：如果唯一这权值和次小生成树不同，否则相同；
#include<stdio.h>
#include<string.h>
#include<map>
#include<iostream>
#include<algorithm>
#include<math.h>
#define N 110
#define INF 0xfffffff using namespace std; int Max[N][N], used[N][N], vis[N], maps[N][N], dist[N], fa[N], n; void Init()
{
memset(vis, , sizeof(vis));
memset(used, , sizeof(used));
memset(Max, , sizeof(Max));
memset(fa, , sizeof(fa));
for(int i=; i<=n; i++)
{
dist[i] = INF;
for(int j=; j<=n; j++)
if(i == j)
maps[i][j] = ;
else
maps[i][j] = INF;
}
} int Prim(int start)
{
int ans=;
for(int i=; i<=n; i++)
{
dist[i] = maps[start][i];
fa[i] = start;
}
vis[start] = ;
for(int i=; i<=n; i++)
{
int Min = INF, index = -;
for(int j=; j<=n; j++)
{
if(vis[j]== && Min > dist[j])
{
Min = dist[j];
index = j;
}
}
if(index == -)break;
vis[index] = ;
ans += Min;
used[fa[index]][index] = used[index][fa[index]] = ;
for(int j=; j<=n; j++)
{
if(vis[j] == && index != j)
{
Max[index][j] = Max[j][index] = max(Max[fa[index]][j], dist[index]);
}
else if(vis[j] == && dist[j] > maps[index][j])
{
dist[j] = maps[index][j];
fa[j] = index;
}
}
}
return ans;
} int SMST(int ans)
{
int Min = INF;
for(int i=; i<=n;i++)
{
for(int j=i+; j<=n; j++)
{
if(used[i][j]== && maps[i][j] != INF)
Min=min(Min, ans-Max[i][j]+maps[i][j]);
}
}
return Min;
} int main()
{
int T, m, a, b, c;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
Init();
for(int i=; i<m; i++)
{
scanf("%d%d%d", &a, &b, &c);
maps[a][b] = maps[b][a] = c;
}
int num1 = Prim();
int num2 = SMST(num1);
if(num1 != num2)
printf("%d\n", num1);
else
printf("Not Unique!\n");
}
return ;
}