poj 1679 判断最小生成树是否唯一(kruskal)

判断最下生成树是否唯一的思路：

1、对图中的每一条边，扫描其他边，如果存在相同权值的边，则对该边做标记。

2、然后用Kruskal算法或Prim算法求MST。

3、求得MST后，如果该MST中未包含做了标记的边，即可判断MST唯一；如果包含做了标记的边，则依次去掉这些边再求MST，如果求得的MST权值和原来的MST的权值一样，即可判断MST不唯一。

针对poj 1679这题，采用Kruskal算法求MST，并判断MST是否唯一：

代码如下：

View Code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 const int N=110;
  5 using namespace std;
  6 
  7 struct Edge{
  8     int u,v,w;  //边的顶点、权值
  9     bool operator < (const Edge &p) const {
 10         return w<p.w;
 11     }
 12     int equal; //标记，1表示存在权值相同的边，0表示不存在
 13     int used;//在第一次求得的MST中，是否包含该边
 14     int del;  //1删除，0未删除
 15 }edge[N*N];
 16 
 17 int n,m;
 18 bool first;
 19 int parent[N];
 20 
 21 //初始化
 22 void UFset(){
 23     for(int i=0;i<n;i++){
 24         parent[i]=-1;
 25     }
 26 }
 27 
 28 int Find(int x){
 29     int s;
 30     for(s=x;parent[s]>=0;s=parent[s]);
 31     //压缩路径，优化
 32     while(s!=x){
 33         int temp=parent[x];
 34         parent[x]=s;
 35         x=temp;
 36     }
 37     return s;
 38 }
 39 
 40 //合并
 41 void Union(int R1,int R2){
 42     int r1=Find(R1);
 43     int r2=Find(R2);
 44     int temp=parent[r1]+parent[r2];
 45     if(parent[r1]>parent[r2]){
 46         parent[r1]=r2;
 47         parent[r2]=temp;
 48     }else {
 49         parent[r1]=temp;
 50         parent[r2]=r1;
 51     }
 52 }
 53 
 54 int kruskal(){
 55     int sumweight=0,num=0;
 56     int u,v;
 57     UFset();
 58     for(int i=0;i<m;i++){
 59         if(edge[i].del==1)continue;//忽略去掉的边
 60         u=edge[i].u,v=edge[i].v;
 61         if(Find(u)!=Find(v)){
 62             sumweight+=edge[i].w;
 63             num++;
 64             Union(u,v);
 65             if(first)edge[i].used=1;
 66         }
 67         if(num>=n-1)break;
 68     }
 69     return sumweight;
 70 }
 71 
 72 int main(){
 73     int u,v,w,t;
 74     scanf("%d",&t);
 75     while(t--){
 76         scanf("%d%d",&n,&m);
 77         for(int i=0;i<m;i++){
 78             scanf("%d%d%d",&u,&v,&w);
 79             edge[i].u=u-1,edge[i].v=v-1,edge[i].w=w;
 80             edge[i].equal=0,edge[i].used=0,edge[i].del=0;
 81         }
 82         // 标记权值相同的边
 83         for(int i=0;i<m;i++){
 84             for(int j=0;j<m;j++){
 85                 if(i==j)continue;
 86                 if(edge[j].w==edge[i].w){
 87                     edge[i].equal=1;
 88                 }
 89             }
 90         }
 91         sort(edge,edge+m);
 92         first=true;
 93         int weight1=kruskal(),weight2;//第一次求MST
 94         first=false;
 95         int tag=1;
 96         for(int i=0;i<m;i++){
 97             if(edge[i].used&&edge[i].equal){
 98                 edge[i].del=1;
 99                 weight2=kruskal();
100                 if(weight1==weight2){
101                     printf("Not Unique!\n");
102                     tag=0;
103                     break;
104                 }
105                 edge[i].del=0;
106             }
107         }
108         if(tag)
109             printf("%d\n",weight1);
110     }
111     return 0;
112 }