MST唯一性判断

2024-02-10 07:18

文章标签 判断唯一性 mst

本文主要是介绍MST唯一性判断，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板题: fzu2087 统计树边

解法（mengxiang000000的博客）

思路：用kruskal算法模拟生成树的过程。同时也是一个贪心生成树的过程，我们知道，生成的树的边权值和是一定的，那么对于边的替换的值也是能够确定的：只有权值相同的边才有可能是另一种生成树方法的边。

然后我就呆萌的记录有多少重边权值的边，然后加上n-1，开开心心的提交，实力WA。一组数据就可以干掉我：
3 3
1 2 1
1 2 2
2 3 1

所以记得一定不要跟我犯一样的错误，我们需要的是动态判断一条边权值相同的边能否可能是另一种生成树方法的边。我们直接在kruskal算法过程中加上动态判断的成分就可以了，那么要如何判断呢？遍历每一条边的时候，如果有相同权值的边，像kruskal一样的判断条件，判断这条边能否加入生成树中即可。

kruskal算法判断一条边是否能够贪心的加入生成树中：

for(int i=0;i<m;i++)   {  if(find(a[i].x)!=find(a[i].y))  {  zhongquanzhi+=a[i].w;  merge(a[i].x,a[i].y);  }   }

我们对同权值的边判断能否加入生成树中，并且别忘记对边要进行入树：

for(int i=0;i<m;i=j)  
{  for(j=i;a[i].w==a[j].w;j++)  {  if(find(a[j].x)!=find(a[j].y))  {  output++;  }  }  for(j=i;a[i].w==a[j].w;j++)  {  if(find(a[j].x)!=find(a[j].y))  {  merge(a[j].x,a[j].y);  }  }  
}

简而言之
如果安全，则先不Union,先统计最小生成树的边数，待统计完后再Union;
poj1679 与此题类似

fzu2087

#include<iostream>
#include<algorithm>
using namespace std;
const int  maxn=100005;typedef struct node{int st,ed,cost;
}Edge ;
Edge edge[100005];
int cmp(Edge a,Edge b){return a.cost<b.cost;
}int fa[maxn];
void init(){for(int i=0;i<maxn;i++)fa[i]= i;
}int Find(int x){if(fa[x] == x)   return fa[x];else  return fa[x] = Find(fa[x]);
}void Union(int x,int y){int fx=Find(x),fy=Find(y);if(fx!= fy)fa[fx] = fy;
}int main(){ios_base::sync_with_stdio(false);int T;cin>>T;while(T--){int n,m,t1,t2,t3;cin>>n>>m;for(int i=0;i<m;i++){cin>>t1>>t2>>t3;edge[i].st=t1,edge[i].ed=t2,edge[i].cost=t3;}sort(edge,edge+m,cmp);int bianshu=0;int tot_cost = 0;init();for(int i=0;i < m ;i++){for(int j=i;edge[j].cost == edge[i].cost;j++)if(Find(edge[j].st)!= Find(edge[j].ed))bianshu++;for(int j=i;edge[j].cost == edge[i].cost;j++)if(Find(edge[j].st)!= Find(edge[j].ed) )Union(edge[j].st,edge[j].ed),tot_cost+=edge[j].cost;}cout<<bianshu<<endl;}
}