prim算法就类似与dijkstra算法从1号点到其他点的最短距离
kruskal算法是先按照边权排序，假如这条边的两个点不连通就加上这条边，假如连通了就跳过
1.最短网络
#include<bits/stdc++.h> using namespace std; const int N=110; int w[N][N]; bool st[N]; int dist[N]; int n,res=0; void prim() { memset(dist,0x3f,sizeof dist); dist[1]=0;//初始化第一个点到自己的距离为0 for(int i=1;i<=n;i++)//找剩下的n个点与第一起点的距离，就像dijkstra一样 { int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j]))//找不在连通块且距离最小的点 t=j; st[t]=true;//标记这个点在连通块内 res+=dist[t]; for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);//用该点更新其他点的最短距离 } } int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>w[i][j]; prim(); cout<<res<<endl; return 0; }
2.局域网
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
相当于一个图中求最小生成树的问题
prim解决
#include<bits/stdc++.h> using namespace std; const int N=110; int w[N][N]; bool st[N]; int dist[N]; int n,res=0,m; void prim() { memset(dist,0x3f,sizeof dist); dist[1]=0;//初始化第一个点到自己的距离为0 for(int i=1;i<=n;i++)//找剩下的n个点与第一起点的距离，就像dijkstra一样 { int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j]))//找不在连通块且距离最小的点 t=j; st[t]=true;//标记这个点在连通块内 res+=dist[t]; for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);//用该点更新其他点的最短距离 } } int main() { int ans=0; cin>>n>>m; memset(w,0x3f,sizeof w); while(m--) { int a,b,c; cin>>a>>b>>c; w[a][b]=w[b][a]=min(w[a][b],c); ans+=w[a][b];//记录所有网线的答案 } prim(); cout<<ans-res<<endl;//输出总的减最小生成数的 return 0; }
kruskal解决
#include<bits/stdc++.h> using namespace std; const int N=110,M=N*N; int n,m; struct Edge { int a,b,w; bool operator < (const Edge&t)const//重载小于号，待会排序就按照w排序 { return w<t.w; } }e[M];//结构体存数 int p[N]; int find(int x)//并查集 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { int ans=0; cin>>n>>m; for(int i=1;i<=n;i++) p[i]=i;//并查集初始化 for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; e[i]={a,b,w}; } sort(e,e+m);//先排序 for(int i=0;i<m;i++) { int a=find(e[i].a),b=find(e[i].b),w=e[i].w; if(a!=b) p[a]=b;//假如不在一个集合，则加上该条边 else ans+=w;//反之该条边就是多余不要的加上答案里 } cout<<ans<<endl;//输出总的减最小生成数的 return 0; }
3.繁忙的都市
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=310,M=N*N; struct Edge { int a,b,w; bool operator < (const Edge&t) const//重载小于号，使排序按照w排 { return w<t.w; } }e[M]; int p[N]; int find(int x)//并查集 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { int n,m,ans; cin>>n>>m; for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; e[i]={a,b,w}; } for(int i=1;i<=n;i++) p[i]=i;//并查集初始化操作 sort(e,e+m);//排序 for(int i=0;i<m;i++) { int a=find(e[i].a),b=find(e[i].b),w=e[i].w; if(a!=b)//假如不在一个连通块中，则加上他 { p[a]=b; ans=w;//更新最大值 } } cout<<n-1<<' '<<ans<<endl; return 0; }
4.联络员
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
这题只能用kruskal，因为有多个连通块，而prim只能处理一个连通块
#include<bits/stdc++.h> using namespace std; const int N=2010,M=1e4+10; int res=0; struct Edge { int a,b,w; bool operator <(const Edge&t)const//重载小于号 { return w<t.w; } }e[M]; int p[N]; int find(int x)//并查集 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { int n,m,cnt=0; cin>>n>>m; for(int i=1;i<=n;i++) p[i]=i;//初始化 for(int i=0;i<m;i++) { int t,a,b,w; cin>>t>>a>>b>>w; if(t&1)//假如是必选 { res+=w;//则加上边权 a=find(a),b=find(b); p[a]=b;//加到同一个连通块中 } else e[cnt++]={a,b,w};//否则非必选 } sort(e,e+cnt);//排序 for(int i=0;i<cnt;i++) { int a=find(e[i].a),b=find(e[i].b),w=e[i].w; if(a!=b)//假如不在一个连通块 { res+=w;//则加上边权 p[a]=b;//加到同一个连通块中 } } cout<<res<<endl; return 0; }
5.连接格点
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
就是给你已经连接了的点，让你加上某些边使他连通，也就是最小生成树，但是不能用prim，可能给出的边有环，只能用kruskal
#include<bits/stdc++.h> using namespace std; const int N=1010,M=N*N,K=2*M; int ids[N][N];//用来将坐标映射到点 int n,m,k; struct Edge { int a,b,w; }e[K]; int p[M]; int find(int x)//并查集 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } void edge() { int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},dw[4]={1,2,1,2};//四个方向 for(int s=0;s<2;s++)//s表示余数，0表示打横走，1表示纵着走 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int u=0;u<4;u++) if(u%2==s)//走的途径 { int x=i+dx[u],y=j+dy[u],w=dw[u]; if(x<=0||x>n||y<=0||y>m) continue;//假如越界 int a=ids[i][j],b=ids[x][y];//获取当前位置 if(a<b) e[k++]={a,b,w};//为了避免重复假如 } } int main() { cin>>n>>m; for(int i=1;i<=n*m;i++) p[i]=i;//初始化 for(int i=1,t=1;i<=n;i++)//映射坐标为点 for(int j=1;j<=m;j++,t++) ids[i][j]=t; int x1,x2,y1,y2; while(cin>>x1>>y1>>x2>>y2) { int a=ids[x1][y1],b=ids[x2][y2]; p[find(a)]=find(b);//假如是连通块了，则加到同个连通块中 } edge();//处理每个走的方式 int res=0; for(int i=0;i<k;i++) { int a=find(e[i].a),b=find(e[i].b),w=e[i].w; if(a!=b)//假如不在一个连通块 { res+=w;//则加上边权 p[a]=b;//加到同一个连通块中 } } cout<<res<<endl; return 0; }
