题目中给出一个无向图,需要判断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; }
党,你这个页面好窄啊。。
次小生成树…
3 3
1 2 3
2 3 2
3 1 3
这组数据不是应该是不唯一的吗?好奇怪啊,你的代码输出了5
能看看 ❓ 吗
我怎么感觉这图是一个最小生成树呢?