题意：求解最小生成树的权值是否唯一，即要我们求次小生成树的权值

两种方法求最小生成树，一种用prim算法， 一种用kruskal算法

 

一：用prim算法

对于给定的图，我们可以证明，次小生成树可以由最小生成树变换一边得到。 那么我们可以如下求给定图的次小生成树。首先，我们用prime算法求出图的最小生成树， 在这个过程中记录每条边是否用过，以及两个点之间最短路径上的最大权值F[i,j]

F[i,j]可以如此求得，当加入点u的时候，并且u的父结点是v 那么对于已经在生成树中的节点x F[x,u] = max(F[x,v],w[u][v])，那么我么就可以用Prime算法一样的时间复杂度来求出图的次小生成树。

参考链接：

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int INF=0x3f3f3f3f;int n,m;int ans1,ans2;int w[101][101];int dis[101];int pre[101];int vis[101]; int use[101][101]; //use[i][j]=1表示边(i,j)在最小生成树里，=0则不在int f[101][101]; //f[u][v]表示结点u到结点v的最短路径上边的最大值(即最大边的值)vector
           
             son[101]; //son[i]存储的是与i连接的端点void init() { memset(pre,0,sizeof(pre)); memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); memset(use,0,sizeof(use));}//求最小生成树int solve_MST() { init(); vector
            
              node; int s=1,counts=0,ans=0,tmp,k; dis[s]=0; pre[s]=s; node.push_back(s); //一开始dis都赋值为INF，所以为了减少一点点遍历的时间，node存储的是dis不为INF的点 while(1) { tmp=INF; for(int i=0; i
            
           
          
         
        
       
      
     

二：用kruskal算法

枚举删除最小生成树上的边，再求最小生成树，即总共求n-1次最小生成树，取其中最小值。

这道题如果用该方法，有一点要注意，不然的话会一直WA。

我做这道题的时候一直wrong answer的原因是因为， 可能求出的次小生成树正好等于最小生成树的总权值，但是它不连通，即边的个数小于n-1

可以试试这个测试数据：

1

6 7

1 3 1

1 2 2

2 3 3

3 4 0

4 5 4

4 6 5

5 6 6

结果是 12

就是说，如果次小生成树不连通,且最小生成树中被你删的边恰好是权值为0的情况， 这样权值总和仍相等，但不满足生成树的要求。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int t,n,m,cost,x,y,w; //n个节点，m条边int ansMST,secondMST;int numOfEdge;struct Edge{    int u,v;    int cost;    bool operator < (const Edge& tmp) const    {        return cost< tmp.cost;    }}edge[5500],MSTedge[210];struct UF{    int father[110];    void unit(){        for(int i=1;i<=n;i++){            father[i]=i;        }    }    int find_root(int x){        if(father[x]!=x)            father[x]=find_root(father[x]);        return father[x];    }    void Union(int fa,int fb){        father[fb]=fa;    }}uf;//求最小生成树int solveMST(){    int counts=0;    int ans=0;    //int index=0;    for(int i=0;i
          
           =n-1){ break; } if(fu!=fv){ ans+=edge[i].cost; uf.Union(fu,fv); MSTedge[counts].u=u; MSTedge[counts].v=v; MSTedge[counts].cost=edge[i].cost; counts++; } } return ans;}/**a、b表示最小生成树中删去的那条边这里是删去(a,b)边后，求最小生成树*/int solve(int a,int b){ int counts=0; int ans=0; for(int i=0;i
           
            =n-1){ break; } if(fu!=fv){ ans+=edge[i].cost; counts++; uf.Union(fu,fv); } } numOfEdge=counts; return ans;}int main(){ scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%d%d",&n,&m); for(int j=0;j