题意:若最小生成树唯一则输出权值和,若不唯一输出Not Not Unique!

分析:首先计算出最小生成树,然后依次删去一条最小生成树的边,判断是否能够新构成权值和以前相等的最小生成树,若能则不唯一

#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;
}
 

发表评论

电子邮件地址不会被公开。

Post Navigation