题意:若最小生成树唯一则输出权值和,若不唯一输出Not Not Unique!
运用prim算法将最小生成树求出,然后在依次枚举删除最小生成树中的每一条边,判断是否还能构成一个新的最小生成树,且权值和与初始的权值和相等,若能构成则不唯一
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
/*看了很久才相处为什么要用这个stl
假设v,u都为最小生成树中的点,但是
v,u所扩展出来的最小生成树边却不一定相等
所以导致数组下标记录u,v显得很不方便,而
vector会将元素加入u,v数组的末尾所以无需知道
数组末尾的下标是多少*/
vector<int>edge[300];
#define INF 99999999
#define MAX 300
int judge;
int map[MAX][MAX];
int vis[MAX];
int Prim(int n,int flag)//这里的flag是0,1,区别就是计算的最小生成树是第一次的还是后来枚举的
{
int lowcost[MAX];
int mst[MAX];
int i,j,min,minid,sum=0;
for (i=1;i<=n;i++)
{
lowcost[i]=INF;
vis[i]=0;
mst[i]=-1;
}
lowcost[1]=0;
for(i=1;i<=n;i++)
{
min=INF;
for (j=1;j<=n;j++)
{
if(lowcost[j]<min && !vis[j])
{
min=lowcost[j];
minid=j;
}
}
sum+=min;
vis[minid]=1;
if(flag)
{
if(mst[minid]!=-1)//以minid为起点的并且加入树中的边加入edge集合
{
edge[mst[minid]].push_back(minid);
}
}
for (j=1;j<=n;j++)
{
if(map[minid][j]<lowcost[j] && !vis[j])
{
lowcost[j]=map[minid][j];
if(flag) mst[j]=minid;
}
}
}
return sum;
}
int main()
{
int T,m,n;
int a,b,c,i,j,ans;
scanf("%d",&T);
while(T--)
{
judge=0;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
map[i][i]=0;
map[i][j]=INF;
}
for(i=0;i<=n;i++)
edge[i].clear();
for (i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
}
ans=Prim(n,1);//f注意这里的1
for (int s=1;s<=n;s++)
{
for (j=0;j<edge[s].size();j++)
{
int t=edge[s][j];//记录起点为s的边
int tmp=map[s][t];//记录st的距离
map[s][t]=map[t][s]=INF;//取消一条边
int temp=Prim(n,0);//注意这里0
map[t][s]=map[s][t]=tmp;//恢复取消的那条边
if(temp==ans)
{
judge=1;
break;
}
}
if(judge) break;
}
if(judge) printf("Not Unique!\n");
else printf("%d\n",ans);
}
return 0;
}