最小生成树模型

题单

最小生成树模型

1.最短网络(prim)

纯裸的一道prim模版题

和dijkstra区别：d数组记录的是一个点到生成树的最小距离

#include<bits/stdc++.h>using namespace std;
int n;
const int N=110,INF=0x3f3f3f3f;
int g[N][N],st[N],d[N];
int res;void prim(){memset(d,0x3f,sizeof d);d[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||d[t]>d[j])){t=j;}}res+=d[t];st[t]=1;for(int j=1;j<=n;j++) d[j]=min(d[j],g[t][j]);}
}signed main(){cin>>n;memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>g[i][j];}}prim();cout<<res<<endl;return 0;
}

2. 局域网(kruskul)

纯裸的kruskul算法

#include<bits/stdc++.h>using namespace std;
int n,k;
const int N=110,M=210;
int fa[N];int find(int x){if(x!=fa[x]) return x=find(fa[x]);return fa[x];
}struct edges{int x,y,z;bool operator<(const edges& M)const{return z<M.z;}
}es[N];signed main(){cin>>n>>k;for(int i=1;i<=n;i++) fa[i]=i;for(int i=0;i<k;i++){int x,y,z;cin>>x>>y>>z;es[i]={x,y,z};}sort(es,es+k);int res=0;for(int i=0;i<k;i++){int a=find(es[i].x),b=find(es[i].y),c=es[i].z;if(a!=b){fa[a]=b;}else{res+=c;}}cout<<res<<endl;return 0;
}

3. 繁忙的都市

思考：

• 题目大意就是要一个最长边最小的最小生成树
• 根据kruskull本身就需要给边排序的特性，直接按序取直到形成一颗生成树
• 这里的最小生成树和传统的权值之和最小的生成树不一样

#include<bits/stdc++.h>using namespace std;
int n,m;
const int N=310,M=8e3+10;
int fa[N];struct edge{int x,y,z;bool operator< (const edge& M)const{return z<M.z;}
}edges[M];int find(int x){if(x!=fa[x]) x=find(fa[x]);return fa[x];
}signed main(){cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i;for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;edges[i]={x,y,z};}sort(edges,edges+m);int res;for(int i=0;i<m;i++){int a=find(edges[i].x),b=find(edges[i].y),c=edges[i].z;if(a!=b){fa[a]=b;res=c;}}cout<<n-1<<' '<<res<<endl;return 0;
}

4. 联络员

第一眼：

• 根据线路分类：可以选择的路 以及 必须存在的路
  • 也就是已知某些边的存在，找到剩下的边，使生成树权值最小（其实不确定还是不是求一颗生成树，但一定要满足每个点都能到，且选择的权值最小
  • 那就直接kruskal算法

//一遍ac
#include<bits/stdc++.h>using namespace std;
const int N=2e3+10,M=1e4+10;
int fa[N];
int n,m;struct edge{int p,x,y,z;bool operator<(const edge& M)const{if(p==M.p){return z<M.z;}return p>M.p;}
}edges[M];int find(int x){if(x!=fa[x]) return x=find(fa[x]);return fa[x];
}signed main(){cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i;int res=0;for(int i=0;i<m;i++){int p,x,y,z;cin>>p>>x>>y>>z;if(p==1){int a=find(x),b=find(y);fa[a]=b;res+=z;}edges[i]={p,x,y,z};}sort(edges,edges+m);for(int i=0;i<m;i++){int a=find(edges[i].x),b=find(edges[i].y),c=edges[i].z;if(a!=b){fa[a]=b;res+=c;}}cout<<res<<endl;return 0;
}

5. 连接格点

还是在已有连线的基础上找到权值之和最小生成树

处理点阵

• (1)把二维压成一维
• (2) 离散化

//第一版代码tle了#include<bits/stdc++.h>using namespace std;
int n,m;
const int N=1e3+10;
int fa[N*N],g[N][N];
int cnt=0;struct edge{int x,y,z;bool operator<(const edge& M)const{return z<M.z;}}edges[2*N*N];int find(int x){if(x!=fa[x]) x=find(fa[x]);return fa[x];
}signed main(){cin>>n>>m;for(int i=1;i<=n*m;i++) fa[i]=i;int x,y,xx,yy;int t=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){g[i][j]=++t;if(i+1<=n){edges[cnt++]={t,t+m,1};}if(j+1<=m)edges[cnt++]={t,t+1,2};}}while(cin>>x>>y>>xx>>yy){int a=find(g[x][y]),b=find(g[xx][yy]);if(a!=b){fa[a]=b;}}sort(edges,edges+cnt);int res=0;for(int i=0;i<cnt;i++){int a=find(edges[i].x),b=find(edges[i].y),c=edges[i].z;if(a!=b){fa[a]=b;res+=c;}}cout<<res<<endl;return 0;
}

边权为正才有最小生成树

小tips：

• 先建纵向边再建横向边，可以省去一步排序过程。

#include<bits/stdc++.h>using namespace std;
int n,m;
const int N=1e3+10;
int fa[N*N],g[N][N];
int cnt;struct edge{int x,y,z;}edges[2*N*N];int find(int x){if(x!=fa[x]) fa[x]=find(fa[x]);//这一步是路径压缩return fa[x];
}void get_edges(){int dx[]={-1,0,1,0},dy[]={0,1,0,-1},dw[]={1,2,1,2};for(int z=0;z<2;z++){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int u=0;u<4;u++){if(u%2==z){int x=i+dx[u],y=j+dy[u],w=dw[u];if(x&&x<=n&&y&&y<=m){int a=g[i][j],b=g[x][y];if(a<b) edges[cnt++]={a,b,w};}}}}}}
}signed main(){cin>>n>>m;for(int i=1;i<=n*m;i++) fa[i]=i;int x,y,xx,yy;int t=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){g[i][j]=++t;}}while(cin>>x>>y>>xx>>yy){int a=find(g[x][y]),b=find(g[xx][yy]);//if(a!=b){//  fa[a]=b;//}fa[a]=b;}get_edges();int res=0;for(int i=0;i<cnt;i++){int a=find(edges[i].x),b=find(edges[i].y),c=edges[i].z;if(a!=b){fa[a]=b;res+=c;}}cout<<res<<endl;return 0;
}