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

于 2011年08月15日 发布在 算法&&ACM 跳到评论

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

本文共有 4条评论 | 沙发:文章评论

  1. 小媛说道:

    党,你这个页面好窄啊。。

  2. acmol说道:

    我怎么感觉这图是一个最小生成树呢?

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)