POJ 1679 The Unique MST (判断MST是否唯一)

POJ 1679 The Unique MST

题目中给出一个无向图，需要判断mst是否唯一。

本题用prim算法来做比较简单，具体来说，当一个节点被两个边更新的时候，如果他被选为下一个放入树中的点，那么连接他的边我们就不能确定了，也就是可能有多个最小生成树。上图，当a点确定的时候，b点更新为8，c点更新为12,然后b被加入树中，然后要更新c点，这时c的值12已经被两条边更新了，所以就可能产生多棵树。

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
const int INF = 2100000000;

using namespace std;
class Edge {
public:
    int to,w;
    Edge *next;
    void add( int t, int ww,Edge *&b){
        to = t;w = ww;next=b;b=this;
    }
};
template<int Vsize, int Esize>
class Prim{
private:
    int countt,N;
    Edge *biao[ Vsize ],A[ 3*Esize ];
    int cnt[ Vsize ];// how many nodes refresh it 
    int d[ Vsize ],flag[ Vsize ];
public:
    void init( int n ){
        countt = 0;N = n;
        for( int i = 0; i <= N; i++ )
            biao[i] = NULL;
    }
    void add( int from,int to,int w ){
        A[ countt++ ].add( to, w, biao[from] );
    }
    
    int prim( void ){
        int i,j,minn,sum = 0,now = 1;
        memset( flag, 0, sizeof(flag) );
        memset( cnt, 0, sizeof(cnt) );
        fill( d, d+Vsize, INF );
        d[ now ] = 0;
        flag[ now ] = 1;
        for( i = 1; i < N; i++ ){
            for(Edge *p = biao[now]; p!=NULL; p = p->next )
                if( !flag[p->to] ){
                    if( d[p->to] > p->w ){
                        d[p->to] = p->w;
                        cnt[p->to] = 1;
                    }
                    else if( d[p->to] == p->w ){
                        cnt[p->to] ++;
                    }
                }
            minn = INF;
            for( j = 1; j <= N; j++ )
                if( !flag[j] && d[j] < minn )
                    minn = d[ now = j ];
            flag[ now ] = 1;
            if( cnt[now] > 1 ) return -1;//返回-1说明mst不唯一
            sum += d[now];
        }
        return sum;
    }
};

Prim< 200 , 20000 > Net;

int main(void){
    int N,M,i,j,k,from,to,w;
    int cases;
    scanf("%d",&cases);
    while( cases-- ){
        scanf("%d%d",&N,&M);
        Net.init( N );
        for( i = 1; i <= M; i++ ){
            scanf("%d%d%d",&from,&to,&w);
            Net.add( from, to, w );
            Net.add( to, from, w );
        }
        w = Net.prim();
        if( w == -1 ) puts("Not Unique!");
        else printf("%d\n",w );
    }
    return 0;
}