ACM-大一训练第三周(Floyd算法+并查集算法专题训练)

🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.CSDN
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​
📣系列专栏：ACM周训练题目合集.CSDN
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️为什么我们不知疲倦，因为我们都在做自己所热爱的事 ♐

---

A - 电车

洛谷：P1346 电车

解题思路：Floyd算法的运用，这里大致讲解一下题目，从第二行开始就是第一个车道 接着就是开关思想，也就是01思想，这里对于电路，或者种树是否这些题目都是一个经验，对于这个题目后面也会对Floyd算法做一个总结

#include<iostream>
#include<cmath>
#include<cstring>using namespace std;#define N  0x3f3f3f3f //一个特别大的数字，记住这个知识点
int n,a,b,m,x,f[1001][1001];int main()
{memset(f,N,sizeof f);//初始化cin>>n>>a>>b;for(int i=1;i<=n;i++)//初始化---自己到自己是0{f[i][i]=0;}for(int i=1;i<=n;i++)//n条道路所以 for循环0-n{cin>>m;//组的变向与不变向for(int j=1;j<=m;j++){cin>>x;if(j==1){f[i][x]=0;//第一个必须设置为0，表示不变向}else {f[i][x]=1;//表示变向的情况}}}//标准的Floyd算法模板for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j || i!=k || j!=k){f[i][j]=min(f[i][k]+f[k][j],f[i][j]);}}}}//输出if(f[a][b]==N) cout<<"-1"<<endl;else cout<<f[a][b]<<endl;return 0;
}

B - 并查集

AcWing—836. 合并集合

解题思路：并查集的模板题目，这里不多赘述。

#include<iostream>using namespace std;const int N=100010;int p[N];
int n,m;int find(int x) //目的：找到父节点 并且返回+路径压缩
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i]=i; //开始只有自己一个元素一个集合while(m--){char op[2];int a,b;scanf("%s%d%d",&op,&a,&b);if(op[0]=='M') p[find(a)]=find(b);else{if(find(a) == find(b)) puts("Yes");else puts("No");}}return 0;
}

C - 最短路

题目来自计蒜客，不过我不知道在哪里找到这个题目，大家下去自己去试一试

解题思路：基础Floyd算法，这个更加模板

#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;int n,m;
int u,v,w;
int g[110][110];
int path[110][110];
const int maxx=99999999;
int main()
{cin>>n>>m;again:for(int i=1;i<=n;i++)//初始化{for(int j=1;j<=n;j++){if(i==j) g[i][j]=0;else g[i][j]=maxx;}}for(int i=1;i<=m;i++)//链接道路{cin>>u>>v>>w;g[u][v]=g[v][u]=w;}for(int k=1;k<=n;k++)//Floyd算法模板{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(g[i][j]>g[i][k]+g[k][j]){g[i][j]=g[i][k]+g[k][j];}}}}printf("%d\n",g[1][n]);//根据题意打印答案cin>>n>>m;if(n==0&&m==0) return 0;else goto again;return 0;
}

D - 修复公路

洛谷：P1111 修复公路

解题思路：并查集思路，不过运用到了结构体的基础知识，模板基础上加一些东西罢了。

#include<iostream>
#include<algorithm>using namespace std;struct node
{int x,y,t;
}a[100010];int n,m,p[100010];int cmp(node a,node b)//按照t进行排序
{return a.t<b.t;
}int find(int x)//并查集算法模板
{return p[x]==x?x:(p[x]=find(p[x]));
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].t);sort(a+1,a+m+1,cmp);for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=m;i++){int px=find(a[i].x);int py=find(a[i].y);if(px!=py) p[px]=py,n--;if(n==1) {cout<<a[i].t;return 0;}}cout<<"-1"<<endl;return 0;
}

E - 青蛙

#include<iostream>
#include<cmath>
#include<cstring>using namespace std;#define inf 0x3f3f3f3fint x[300],y[300],n;
double g[300][300];int main()
{int q=1;while(cin>>n&&n){memset(g,inf,sizeof(g));for(int i=1;i<=n;i++){cin>>x[i]>>y[i];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]=g[j][i]=sqrt(double(x[i]-x[j])*(x[i]-x[j])+double(y[i]-y[j])*(y[i]-y[j]));}}for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)g[i][j]=min(g[i][j],max(g[i][k],g[k][j]));printf("Scenario #%d\nFrog Distance = %.3lf\n\n",q++,g[1][2]);}
}

F - 炸铁路

P1656 炸铁路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>using namespace std;#define inf ox3f3f3f3f
int n,m,f[151],b[151];
struct City
{int a,b;
}p[5010];int find(int x)
{if(f[x]==x) return x;else return f[x]=find(f[x]);
}bool cmp(City x,City y)
{if(x.a==y.a) return x.b<y.b;return x.a<y.a;
}void he(int x,int y)
{int x1=find(x),y1=find(y);f[y1]=f[x1];
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>p[i].a>>p[i].b;if(p[i].a>p[i].b){int t=p[i].a;p[i].a=p[i].b;p[i].b=t;}}sort(p+1,p+m+1,cmp);for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){f[j]=j;}for(int j=1;j<=m;j++){if(j!=i){he(p[j].a,p[j].b);}}for(int j=2;j<=n;j++){if(f[find(j)]!=f[find(j-1)]){cout<<p[i].a<<" "<<p[i].b<<endl;break;}}}return 0;
}

G - DZY热爱化学

题目来自cf，具体我这里不链接了。

解题思路：并查集思路，模板基础上加一些东西罢了。

#include<iostream>
#include<cmath>using namespace std;typedef long long ll;
const int N=100010;
int p[N];
int n,m;int find(int x)
{return p[x]==x?x:(p[x]=find(p[x]));
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++) p[i]=i;if(m==0){printf("1");return 0;}while(m--){int a,b;cin>>a>>b;a=find(a);b=find(b);if(a!=b){p[a]=b;}}ll ans=0,cnt=0;for(int i=1;i<=n;i++){if(find(i)!=i){++ans;}}ll c=pow(2,ans);printf("%lld\n",c);return 0;
}

H - 合根植物

P8654 [蓝桥杯 2017 国 C] 合根植物

解题思路：并查集思路，模板基础上加一些东西罢了。

#include<iostream>
#include<cmath>using namespace std;int n,m,k;
int p[100000010];int find(int x)
{return p[x]==x?x:(p[x]=find(p[x]));
}int main()
{cin>>n>>m>>k;int res=n*m;for(int i=1;i<=res;i++) p[i]=i;int ans=0;while(k--){int a,b;cin>>a>>b;a=find(a);b=find(b);if(a!=b){p[a]=b;}}for(int i=1;i<=res-1;i++){if(find(i)!=find(i+1)){ans++;p[find(i)]=find(i+1);}}cout<<ans+1<<endl;return 0;
}

总结

并查集：
做题思路：你会发现，你只需要输入操作+合并也就是find函数
再进行for循环遍历一遍就可以得到答案，不信你可以看看我写
的那些题目的共同特点真的非常相似，或许因为初学的缘故真的会发现
非常简单，因为就是这样用的

Floyd算法：

初始化+三层for循环+输出基本就是这个算法的模板，但是最困难的是建图的过程，这个需要特别训练