Kruskal

2019-11-08 02:56:02

字体：大中小

来源：转载

供稿：网友

Kruskal求最小（大）生成树

模板

思路：将边排序，依次向并查集里加边，并且保证此边连接的两个结点不在一个并查集里，加到N-1（N为图中结点数）条边时，就生成了最小生成树

#include<iostream> #include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;int ecnt;struct node{int from,to,value;} edge[100001];void add(int from,int to,int value){ ecnt++; edge[ecnt].from=from; edge[ecnt].to=to; edge[ecnt].value=value;}int fath[100001];int getfath(int x){ if(fath[x]==x) return x; return fath[x]=getfath(fath[x]);}void unionset(int x,int y){fath[getfath(x)]=getfath(y);}int cmp(const node &a,const node &b){ if(a.value<b.value) return true; else return false;}long long mstv=0,biancnt=0;int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int from,to,value;int x; for(int i=1;i<=m;i++) { cin>>from>>to>>value; add(from,to,value); } for(int i=1;i<=n;i++) fath[i]=i; sort(edge+1,edge+ecnt+1,cmp); for(int i=1;i<=m;i++) { if(getfath(edge[i].from)!=getfath(edge[i].to)) { unionset(edge[i].from,edge[i].to); mstv+=edge[i].value; biancnt++; } if(biancnt==n-1) break; } cout<<mstv; return 0;}

例题

UVa1395 Slim_Span

所谓的Slim Span即为最大边与最小边差值最小的生成树，与最小生成树问题的思路相似

先对边升序排序，对于一个连续的边区间[L,R] $[L,R]$ ，从小到大枚举L，对于每个L，从小到大枚举R，依次向并查集里加边，加个判断：如果目前的这些边已经使得图连通，就停止枚举，并更新最小值。

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int MAXN=100,MAXM=50*99,INF=1<<30;struct node2{int u,v,w;} a[MAXM+1];int acnt;void add2(int u,int v,int w){++acnt,a[acnt].u=u,a[acnt].v=v,a[acnt].w=w;}int fa[MAXN+1];int getfa(int x){ if(fa[x]==x) return x; return fa[x]=getfa(fa[x]);}void join(int x,int y){ fa[getfa(x)]=getfa(y);}bool cmp(const node2 & a,const node2 & b){return a.w<b.w;}int N,M;int main(){ int i; while(cin>>N>>M&&N) { acnt=0; for(i=1;i<=N;i++) fa[i]=i; for(i=1;i<=M;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add2(u,v,w); }sort(a+1,a+M+1,cmp); int L,R; int minv=INF; for(L=1;L<=M-(N-1)+1;L++) { for(i=1;i<=N;i++) fa[i]=i; int times=0; for(R=L;R<=M;R++) if(getfa(a[R].u)!=getfa(a[R].v)) { join(a[R].u,a[R].v); ++times; if(times==N-1) { minv=min(minv,a[R].w-a[L].w); break; } } } if(minv==INF) cout<<-1<<endl; else cout<<minv<<endl; } return 0;}

上一篇：BZOJ 2288: 【POJ Challenge】生日礼物贪心，堆 BZOJ 1150强化

下一篇：PAT 1058

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注