poj 1679 The Unique MST

点击打开链接poj 1679

思路：最小生成树+次小生成树
分析：判断最小生成树是否是唯一的，那就可以去判断次小生成树是否大于最小生成树。这里就涉及到了次小生成树的求法
求解次小生成树：
step 1.  先用prim求出最小生成树T.
             在prim的同时，用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的
             路中权值最大的那条边的权值. (注意这里).
             这是很容易做到的，因为prim是每次增加一个结点s, 而设已经标号了的结点
             集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
             step 1 用时 O(V^2).
step 2.  枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
#define INF 0XFFFFFFF

int t , n , m;
int vis[MAXN];
int pre[MAXN];/*记录节点的上一个节点*/
int lowcost[MAXN];
int maxvalue[MAXN][MAXN];
int G[MAXN][MAXN];
int mark[MAXN][MAXN];/*标记还有哪些边没被用*/

/*初始化*/
void init(){
    memset(mark , 0 , sizeof(mark));
    memset(maxvalue , 0 , sizeof(maxvalue));
    for(int i = 1 ; i <= n ; i++){
        pre[i] = 1;/*把所有点的上一点都记录为1*/
        for(int j = 1 ; j <= n ; j++)
           G[i][j] = INF;
    }
}

/*prime算法*/
void prime(){
     /*求解最小生成树*/
     memset(vis , 0 , sizeof(vis));
     int ans , pos , min;
     ans = 0;
     vis[1] = 1;
     for(int i = 1 ; i<= n ; i++)
         lowcost[i] = G[1][i];
     for(int i = 1 ; i <= n ; i++){
         pos = -1;
         for(int j = 1 ; j <= n ; j++){
            if(!vis[j] && (pos == -1 || lowcost[j] < lowcost[pos]))
              pos = j;
         }
         vis[pos] = 1;
         ans += lowcost[pos];
         mark[pre[pos]][pos] = mark[pos][pre[pos]] = 0;
         for(int j = 1 ; j <= n ; j++){
             if(vis[j])/*记录maxalue数组*/
                 maxvalue[j][pos] = maxvalue[pos][j] = lowcost[pos];
             if(!vis[j] && lowcost[j] > G[j][pos]){
                 lowcost[j] = G[j][pos];
                 pre[j] = pos;/*记录这些点的上一个节点*/
             }
         }
     }
     /*求解次小生成树*/
     min = INF;
     for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ;j++){
           if(mark[i][j]){
             int tmp = ans-maxvalue[i][j]+G[i][j];
             if(tmp < min)
                 min = tmp;
             mark[i][j] = mark[j][i] = 0;
           }
        } 
     }
     if(ans < min)/*如果不同则说明最小生成树是唯一的*/
         printf("%d\n" , ans);
     else
         printf("Not Unique!\n");
}

int main(){
    int x , y , v;
    scanf("%d" , &t);    
    while(t--){
       scanf("%d%d" , &n , &m);
       init();
       for(int i = 0 ; i < m ; i++){
          scanf("%d%d%d" , &x , &y , &v);
          if(G[x][y] > v){
              G[x][y] = G[y][x] = v;
              mark[x][y] = mark[y][x] = 1;
          }
       }
       prime();
    }
    return 0;
}