题目大意】
给出一个带权无向图，问其最小生成树是否唯一，若唯一输出其权值和，否则输出"Not Unique!".
1.其实，在判断最小生成树是否是唯一的时候，用到了次小生成树的思想，求一棵次小生成树，最次小生成树的总权值等于最小生成树的权值，则不唯一；
这里涉及到求次小生成树的问题，首先用prim 算法求一个最小生成树， 再做一次添边和删边的操作，添加一条最小生成树外的边，此时必在最小生成树上形成环，在删去环上权值最大的边，求出添删操作中差额最小值，若最小值为0，则不唯一，否则唯一；（这里我是这样做的，在pime算法求最小生成树的过程中，有一个增加生成树节点的操作，每增加一个节点，则求出该节点到生成树上每一个点的路径上的最大边）
2.第二种判断方法，在pime算法过程中，若某个点i的D[i]被确定时，D[i]能够被2个或以上的点更新得到，那么MST显然不唯一。
判断方法一：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int g[110][110],n,m,ans,d[110],pre[110];
int max1[110][110],stack[110];
bool flag[110];
//max1[i][j]表示i 到j路径上最大边的值
void prim()
{
memset(flag,false,sizeof(flag));
flag[1]=0;
for(int i=2;i<=n;i++)
{
pre[i]=1;
d[i]=g[1][i];
}
d[1]=0;
ans=0;
int top=0;
stack[top++]=1;//保存最小生成树上的节点
for(int i=1;i<n;i++)
{
int tmp=INT_MAX,t=1;
for(int j=2;j<=n;j++)
{
if(!flag[j]&&d[j]!=-1&&d[j]<tmp)
t=j,tmp=d[j];
}
flag[t]=true;
ans+=tmp;
for(int i=0;i<top;i++)//求出当前找到的节点到最小生长树上每一个点的路径上的最大边
max1[stack[i]][t]=max1[t][stack[i]]=max(max1[pre[t]][stack[i]],tmp);
stack[top++]=t;
for(int j=1;j<=n;j++)
{
if(!flag[j]&&g[t][j]!=-1&&(g[t][j]<d[j]||d[j]==-1))
{
d[j]=g[t][j];
pre[j]=t;//记录直接前驱
}
}
}
}
int main()
{
int cas;
int a,b,c;
scanf("%d",&cas);
while(cas--)
{
memset(g,-1,sizeof(g));
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&a,&b,&c);
g[a][b]=g[b][a]=c;
}
memset(max1,-1,sizeof(max1));
prim();
int min1=INT_MAX;
for(int i=1;i<=n;i++)//枚举最小生成树外 的边
for(int j=1;j<=n;j++)
if(i!=j&&i!=pre[j]&&j!=pre[i]&&g[i][j]>0)
min1=min(g[i][j]-max1[i][j],min1);
if(min1) cout<<ans<<endl;
else cout<<"Not Unique!"<<endl;
}
return 0;
}
判断方法二：
#include<cstdio>
#include<cstdlib>
#define N 110
const int inf=10000000;
int n,m,a[N][N],d[N],v[N],s,change[N];
void init(){
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
a[i][j]=inf-1;
for (int i=0;i<m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
a[x][y]=a[y][x]=z;
}
for (int i=1;i<=n;i++)
v[i]=0,d[i]=inf,change[i]=0;
return;
}
bool solve(){
s=0;
d[1]=0;
for (int t=0;t<n;t++){
int min=inf,k=0;
for (int i=1;i<=n;i++)
if (!v[i]&&d[i]<min){
min=d[i];
k=i;
}
if (!k) break;
v[k]=1;
if (change[k]>=2) return 0;
s+=min;
for (int i=1;i<=n;i++)
if (!v[i])
if (a[k][i]<d[i])d[i]=a[k][i],change[i]=1;
else if (a[k][i]==d[i])
change[i]++;
}
return 1;
}
int main(){
int tests;
scanf("%d",&tests);
for (int i=0;i<tests;i++){
init();
if (solve()) printf("%d\n",s);
else printf("Not Unique!\n");
}
}