2023首届大学生算法大赛 - 村庄

 

---

读题可以发现，如果两个村庄不能互相连通，那就算作一对 （a<b）。

显然是可以用floyd全局多源最短路来做的，如果不存在最短路，那么就是不能互通，但是这道题的数据范围N<=10^5，跑floyd复杂度为O（n^3）即10^15远大于10^8，显然是不行，复杂度级别只能是O（n），线性的，或者O（nlogn）。

看一下样例说明

显然如果两个村庄位于同一个连通块中，必然找不出（a<b），如果不在同一个连通块中，必然会产生（a<b），且数量刚好是第一个连通块的村庄数量 乘以 第二个连通块的数量。

为什么？

假设下图，1和2相连，3和4相连。

 明显可以发现1与3,4，都不相连，产生了第二个连通块村庄数量的（a<b）

2与3,4，也不相连，即为2*2=4。

所以直接使用并查集：【模板】并查集 - 洛谷

初始给每个村庄都分配一个连通块，如果有桥相连，就把它们加入同一个连通块。

因为会摧毁编号为1~k的桥，所以输入的时候只需要i>k的部分，不需要合并被摧毁的部分。

 

细节（以样例说明）：第四座桥把4接到了连通块1上，第五座桥把1接到了连通块3上，这里就出现了一个问题，4并没有被更新，所以最后还要再跑一遍find，更新所有情况。（本蒟蒻考试的时候熬夜昏迷了，没想到这一点）

应该能AC的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int n,m,k,u,v,f[100001],cnt,ans;
bitset<100001>vis;
int a[100001];//连通块编号,其中村庄数量
vector<int>a_;
//定义f[i]=j为：i村庄在连通块j中
int find(int x){
    if(f[x]==x)return x;
    else return f[x]= find(f[x]);
}
void unit(int x,int y){
    x= find(x),y= find(y);
    f[x]=y;
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)//初始化每个村庄的连通块
        f[i]=i;
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        if(i>k){//1~k的桥全部被摧毁,只需要i>k的桥
            unit(u,v);
        }
    }
 
    for(int i=1;i<=n;++i)//跑一遍find,更新最终情况
        find(i);
    for(int i=1;i<=n;++i){//累计连通块编号
        a[f[i]]++;
    }
    for(int i=1;i<=n;++i)//把累计完的连通块全部拿出来
        if(a[i])a_.push_back(a[i]);
    for(int i=0;i<a_.size();++i)//配对连通块,累计答案
        for(int j=i+1;j<a_.size();++j)
            ans+=a_[i]*a_[j];
 
    cout<<ans;
    return 0;
}

如果有错误或者有更好的思路，欢迎评论！

看看算法大赛还会不会开放OJ让我们再次测试。

同时预祝各位在2023/4/8的蓝桥杯省赛中while(true)rp++

别熬夜 : )