网站建设公司做销售好不好/sem投放是什么意思

学习最小生成树之前我们首先来学习一下并查集

相关的博客：https://blog.csdn.net/qq_44797733/article/details/104693392?

然后最小生成树的算法大部分都是用加边法Kruskal 算法来写的

 

 

 

 

 

 

 

Highways

 

思路：

求最小生成树中的最长的边，并且要使这个最长的边要尽可能的小，这符合最小的生成树的思想，边从小到大找到符合要求的n-1条边

 

 

code：

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;const int M=3e5+10;
const int N=550;
int G[N][N];
int n;
int fa[N];
int cnt;
struct node{int from,to;int dis;
}e[M];bool cmp(node a,node b){return a.dis<b.dis;
}int get(int x){if(fa[x]==x) return x;else return fa[x]=get(fa[x]);
}int main()
{int t;scanf("%d",&t);while(t--){int ans;scanf("%d",&n);for(int i=1;i<=n;i++) fa[i]=i;cnt=0;for(int i= 1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&G[i][j]);}for(int i=1;i<=n-1;i++)for(int j=i+1;j<=n;j++){e[cnt].from=i;e[cnt].to=j;e[cnt++].dis=G[i][j]; }sort(e,e+cnt,cmp);int k=0;for(int i=0;i<cnt;i++){if(k==n-1) break;int dx=get(e[i].from),dy=get(e[i].to);if(dx!=dy){k++;ans=e[i].dis;fa[dx]=dy;}} printf("%d\n",ans);
//		puts("");}return 0;} 

 

 

Networking

 

最小生成的板子，记得有重边的，取最小的边就可以

 

 

code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3fusing namespace std;const int N=55;
const int M =1e4+10;
int n,m;
int G[N][N];
int fa[N];
int cnt;
struct node{int from,to;int dis;
}e[M]; bool cmp(node a,node b){return a.dis<b.dis;
}
int get(int x){if(fa[x]==x) return x;else return fa[x]=get(fa[x]);
}
int main(){while(~scanf("%d",&n)&&n!=0){for(int i=1;i<=n;i++) fa[i]=i;cnt=0;int a,b,c;memset(G,INF,sizeof G);scanf("%d",&m);while(m--){scanf("%d%d%d",&a,&b,&c); G[a][b]=G[b][a]=min (G[a][b],c);} for(int i=1;i<=n-1;i++)for(int j=i+1;j<=n;j++){e[cnt].from=i;e[cnt].to=j;e[cnt++].dis=G[i][j];}sort(e,e+cnt,cmp);int ans=0;int k=0;for(int i=0;i<cnt;i++){if(k==n-1 ) break;int dx=get(e[i].from),dy=get(e[i].to);if(dx!=dy){fa[dx]=dy;k++;ans+=e[i].dis;}}printf("%d\n",ans);} return 0;
}

 

 

The Suspects

 

思路：m个群体，里面有些群体可能就是一个群体，利用并查集把与0有关的放在一起，计算一下数量即可

code：

#include<iostream>
#include<cstdio>using namespace std;const int N=3e4+10;int n,m;
int fa[N],si[N];int get(int x){if(x==fa[x]) return x;else return fa[x]=get(fa[x]);
}void merge(int x,int y){int tx=get(x),ty=get(y);if(tx!=ty){fa[tx]=ty;si[ty]+=si[tx];//计算一个队的元素的个数 }
}
int main()
{while(~scanf("%d%d",&n,&m)&&(n||m)){for(int i=0;i<n;i++){fa[i]=i;si[i]=1;}int num;while(m--){int a[N];scanf("%d",&num);for(int i=1;i<=num;i++) scanf("%d",&a[i]);for(int i=2;i<=num;i++) merge(a[i],a[1]);}int ans=si[get(0)];printf("%d\n",ans);}return 0;
}

 

 

 

Cube Stacking

 

加权并查集

 

#include<iostream>
#include<cstdio>using namespace std;const int N=3e4+10;
const int M=3e4;
int n,m;
int fa[N],si[N],hi[N];//si表示根节点所在的集合的元素个数 hi表示节点下方的元素的个数 int get(int x){if(x==fa[x]) return x;else{int t= fa[x];//记录当前层次的父亲节点 fa[x]=get(t);//跟新当前层次的父亲节点并进入下一层次hi[x]+=hi[t];//回溯一下当前节点  意思就是本身的加上他的父亲增加的 return fa[x]; } 
}
void merge(int x,int y){int tx=get(x),ty=get(y);if(tx!=ty){fa[tx]=ty;hi[tx]=si[ty];si[ty]+=si[tx];//计算一个队的元素的个数 }
}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);for(int i=1;i<=M;i++) fa[i]=i,si[i]=1,hi[i]=0;cin>>n;while(n--){char ch;cin>>ch;int a,b;if(ch=='M'){cin>>a>>b;merge(a,b); }else{cin>>a;get(a);icout<<hi[a]<<"\n";}	}return 0;
}

 

 

 

畅通工程

 

 

注意路有可能建不完，只有不是一个集合的才能建路，最后的路一定是m-1条否则就输出？

 

 

code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 110;
const int M= 2e5+10;int fa[N];
int n,m;
int k;
struct node{int from,to;int dis;
}e[M];bool cmp(node a,node b){return  a.dis<b.dis;
}int get(int x ){if(x==fa[x]) return x;return fa[x]=get(fa[x]);
}int main()
{while(~scanf("%d%d",&n,&m)&&n!=0){k=0;for(int i=1;i<=m;i++) fa[i]=i;	for(int i=0;i<n;i++){scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].dis);}sort(e,e+n,cmp);int ans=0;for(int i=0;i<n;i++){if(k==m-1) break;int dx=get(e[i].from),dy=get(e[i].to);if(dx!=dy){fa[dx]=dy;k++;ans+=e[i].dis;}}if(k==m-1) printf("%d\n",ans);else puts("?");}} 

 

 

How Many Tables

 

 

求集合数量

code：

#include<iostream>
#include<cstdio>using namespace std;const int N=1100;
int fa[N];
int n,m;
int t;int get(int x ){ if(x==fa[x]) return x;return  fa[x]=get(fa[x]);
}void merge(int  x,int y){int dx=get(x),dy=get(y); if(dx!=dy) fa[dx]=dy;
}int main()
{scanf("%d",&t); while( t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) fa[i]=i;int a,b;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);merge(a,b);}int ans=0;for(int i=1;i<=n;i++){
//			cout<<fa[i]<<endl;if(fa[i]==i) ans ++;}printf("%d\n",ans);}return 0;
}