POJ 1679 判断最小生成树是否唯一

题目大意：

　　给定一个n个点，m条边的无向图，(1<=n<=100，1<=m<=10000，因为保证没有重边)，问这个图的最小生成树（MST）是否唯一。

分析：

　　我的做法是第一次先用Prim算法做一次MST得到最终的权值total，并且标记所用的边（共n-1条），然后单独分别地枚举第一次做Prim时标记的边，对于枚举到的边，在原图里删除之，做一次MST看权值和第一次的total是否相等，如果相等说明MST不唯一，直到枚举完所有标记的边后还是没有判断到不唯一那么说明是唯一的，具体见代码，我觉得我的代码还是写得不错的，这得感谢fatboy_cw的头文件。

代码：

poj1679

 1 /*1679    Accepted    340K    16MS    C++    2170B    2012-04-19 11:17:19*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 
10 #define mpair make_pair
11 #define pii pair<int,int>
12 #define MM(a,b) memset(a,b,sizeof(a));
13 typedef long long lld;
14 typedef unsigned long long u64;
15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
17 #define maxn 110
18 #define inf 100000000
19 
20 int n,m;
21 int g[maxn][maxn], t[maxn][maxn];
22 
23 int dis[maxn];
24 int pre[maxn];
25 bool vis[maxn];
26 bool Flag;
27 int Prim(){
28     for(int i=1;i<=n;++i) dis[i]= inf, vis[i]= 0;
29     for(int i=1;i<=n;++i){
30         if( up_min( dis[i], t[i][1] ) )
31             if( Flag ) pre[i]= 1;
32     }
33 
34     vis[1]= 1;
35     int ret= 0;
36     for(int k=1;k<n;++k){
37         int minval= inf, idx= -1;
38         for(int i=1;i<=n;++i){
39             if( !vis[i] && up_min( minval, dis[i] ) )
40                 idx= i;
41         }
42         if( -1 == idx ) return -1;
43         vis[ idx ]= 1;
44         ret+= dis[ idx ];
45         for(int i=1;i<=n;++i){
46             if( !vis[i] && up_min( dis[i], t[i][idx] ) )
47                 if( Flag ) pre[i]= idx;
48         }
49     }
50     return ret;
51 }
52 
53 void Copy(){
54     for(int i=1;i<=n;++i)
55         for(int j=1;j<=n;++j)
56             t[i][j]= g[i][j];
57 }
58 
59 int main()
60 {
61     int T,u,v,w,i,j;
62     cin>>T;
63     while(T--){
64         scanf("%d%d", &n, &m);
65         for(i=1;i<=n;++i)
66             for(j=1;j<=n;++j)
67                 g[i][j]= (i==j ? 0 : inf);
68 
69         for(i=1;i<=m;++i){
70             scanf("%d%d%d", &u, &v, &w);
71             g[u][v]= g[v][u]= w;
72         }
73         Copy();
74 
75         Flag= 1;
76         int total= Prim();
77         Flag= 0; ///
78 
79         if( -1 == total ){
80             puts("0");
81             continue; /// ???
82         }
83 
84         for(i=2;i<=n;++i){
85             Copy();
86             t[ pre[i] ][i]= inf;
87             t[i][ pre[i] ]= inf;
88             int ret= Prim();
89             if( ret==total ) break;
90         }
91         if( i>n ) printf("%d\n", total);
92         else puts("Not Unique!");
93     }
94 }

一毛原创作品，转载请注明出处。