最小生成树

最小生成树问题是指给定一个带权的无向图，删除一些边使得这个无向图变成一棵树，并且权值之和最小。

解决此类问题的方法主要有两种：Prim算法，Kruskal算法

Prim 算法

从一个点开始，逐步扩展，每次选择权值最小的相连的边，保证不出环，直到顶点总数等于图中所有顶点个数，组成最小生成树

例题 最小生成树

P3366 【模板】最小生成树

#include<bits/stdc++.h>
using namespace std;
int fa[500005],n,m,ans,cnt;
int vis[100005],dis[100005],g[5005][5005];
void prim(){memset(vis,0,sizeof vis);memset(dis,0x3f,sizeof dis);dis[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++){if(!vis[j]&&(t==-1||dis[j]<dis[t])){t=j;}}if(dis[t]==0x3f3f3f3f){printf("orz\n");return ;}vis[t]=1;ans+=dis[t];for(int j=1;j<=n;j++){if(dis[j]>g[t][j]&&!vis[j]){dis[j]=g[t][j];}}}printf("%d\n",ans);
}
int main(){scanf("%d%d",&n,&m);memset(g,0x3f,sizeof g);for(int i=1;i<=m;i++){ int xx,yy,zz;scanf("%d%d%d",&xx,&yy,&zz);if(g[xx][yy]==0x3f3f3f3f){g[xx][yy]=zz;g[yy][xx]=zz;}else{g[xx][yy]=min(zz,g[xx][yy]);g[yy][xx]=min(zz,g[yy][xx]);}}prim();return 0;
}

Kruskal 算法

把所有边都从小到大排好序，从小到大逐个放入树，保证不能出环，直至树中结点总个数等于原无向图顶点数

例题 最小生成树

P3366 【模板】最小生成树

#include<bits/stdc++.h>
using namespace std;
int fa[100005],n,m,ans,cnt;
struct node{int x,y,z;
}a[200005];
int Find(int x){if(fa[x]==x){return x;}return fa[x]=Find(fa[x]);
}
bool cmp(node aa,node bb){return aa.z<bb.z;
}
int kruskal(){sort(a+1,a+m+1,cmp);for(int i=1;i<=m;i++){int xx=Find(a[i].x);int yy=Find(a[i].y);if(xx==yy){continue;}ans+=a[i].z;fa[yy]=xx;if(++cnt==n-1){return ans;}}return -1;
}
void Init(){for(int i=1;i<=n;i++){fa[i]=i;}
}
int main(){scanf("%d%d",&n,&m);Init();for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);}if(kruskal()==-1){printf("orz\n");return 0;}printf("%d\n",ans);return 0;
}

Build

给定几个城镇的坐标，要让它们联通起来，在它们间

#include<bits/stdc++.h>
using namespace std;
long long fa[500005],n,ans,cnt;
struct node2{long long x,y,z;
}b[500005];
struct node{long long x,y,z;
}a[500005];
long long Find(long long x){if(fa[x]==x){return x;}return fa[x]=Find(fa[x]);
}
bool cmp1(node2 aa,node2 bb){return aa.x<bb.x;
}
bool cmp2(node2 aa,node2 bb){return aa.y<bb.y;
}
bool cmp(node aa,node bb){return aa.z<bb.z;
}
void kruskal(){sort(a+1,a+2*n+1,cmp);for(int i=1;i<=2*n;i++){long long x=a[i].x;long long y=a[i].y;long long xx=Find(x);long long yy=Find(y);if(xx==yy){continue;}fa[xx]=yy;ans+=a[i].z;cnt++;if(cnt==n-1){return ;}}
}
void Init(){for(int i=1;i<=n;i++){fa[i]=i;}
}
int main(){scanf("%lld",&n);Init();for(int i=1;i<=n;i++){ scanf("%lld%lld",&b[i].x,&b[i].y);b[i].z=i;}sort(b+1,b+n+1,cmp1);for(int i=1;i<n;i++){a[i].x=b[i].z;a[i].y=b[i+1].z;a[i].z=b[i+1].x-b[i].x;}sort(b+1,b+n+1,cmp2);for(int i=1;i<n;i++){a[i+n].x=b[i].z;a[i+n].y=b[i+1].z;a[i+n].z=b[i+1].y-b[i].y;}kruskal();printf("%lld\n",ans);return 0;
}