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

桃扇骨 2024-04-24 23:20 75阅读 0赞

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

#### 文章目录 ####

*  A - 电车
 *  B - 并查集
 *  C - 最短路
 *  D - 修复公路
 *  E - 青蛙
 *  F - 炸铁路
 *  G - DZY热爱化学
 *  H - 合根植物
 *  总结

--------------------

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]

## A - 电车 ##

[洛谷：P1346 电车][P1346]  
![在这里插入图片描述][6616bf19d3e54a159f8efa10c5550b40.png]  
解题思路：`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. 合并集合][AcWing_836.]  
![在这里插入图片描述][37c84a4fb3d8439c829ddb2f5e063ab4.png]  
解题思路：并查集的模板题目，这里不多赘述。

#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 - 最短路 ##

![在这里插入图片描述][50beeca91740493dad89f8aadcd2759f.png]  
题目来自计蒜客，不过我不知道在哪里找到这个题目，大家下去自己去试一试

解题思路：基础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 修复公路][P1111]  
![在这里插入图片描述][4ed479ed6fb54776a69fd91541a18631.png]  
解题思路：并查集思路，不过运用到了结构体的基础知识，模板基础上加一些东西罢了。

#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 - 青蛙 ##

![在这里插入图片描述][c6fd3558155b495aa6f2b98908587eb8.png]

#include<iostream>
    #include<cmath>
    #include<cstring>
    
    using namespace std;
    
    #define inf 0x3f3f3f3f
    
    int 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 炸铁路][P1656]  
![在这里插入图片描述][9d297e220ef043cf9a455ccf3229c461.png]

#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，具体我这里不链接了。  
![在这里插入图片描述][132f031821254dd2a88085d25ae07bd9.png]  
解题思路：并查集思路，模板基础上加一些东西罢了。

#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\] 合根植物][P8654 _ 2017 _ C_]  
![在这里插入图片描述][bcb0bab6e9004576b59b43a4ad4150e6.png]  
解题思路：并查集思路，模板基础上加一些东西罢了。

#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循环`\+`输出`基本就是这个`算法的模板`，但是最困难的是`建图的过程`，这个需要`特别训练`

[.CSDN]: https://blog.csdn.net/congfen214?type=blog
[ACM_.CSDN]: https://blog.csdn.net/congfen214/category_12101464.html?spm=1001.2014.3001.5482
[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/022f9e8c86814c56b10f0e442100fcf0.gif
[P1346]: https://www.luogu.com.cn/problem/P1346
[6616bf19d3e54a159f8efa10c5550b40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/6e844010e7cd4c37b0213db5eeb8deed.png
[AcWing_836.]: https://www.acwing.com/problem/content/838/
[37c84a4fb3d8439c829ddb2f5e063ab4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/b57a1479e05b47258cd2676e2d2b6763.png
[50beeca91740493dad89f8aadcd2759f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/203379acf6d94ca2b9f277c761918a3f.png
[P1111]: https://www.luogu.com.cn/problem/P1111
[4ed479ed6fb54776a69fd91541a18631.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/814f8b3ea7814a7f8e2ed1b27d3d20a6.png
[c6fd3558155b495aa6f2b98908587eb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/9e76acfc46be4760986bb6dbc6c824b0.png
[P1656]: https://www.luogu.com.cn/problem/P1656
[9d297e220ef043cf9a455ccf3229c461.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/995cd9bed3be4db5adb66856058a1f18.png
[132f031821254dd2a88085d25ae07bd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/79b990ce5ec741a0b451d6900e460788.png
[P8654 _ 2017 _ C_]: https://www.luogu.com.cn/problem/P8654
[bcb0bab6e9004576b59b43a4ad4150e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/dbeb6cd862bc4377a6f556c2b24637cc.png