P11674 [USACO25JAN] Reachable Pairs G

· · 题解

前言

本题属于思维题，本人在结束后 10min 想到了正确做法，写个题解纪念一下。

思路

我们仔细观察题目的两个操作，发现包括了删除节点和加入边，一个是删除一个是加入，不是很好处理，于是思考如何转化。

手动模拟一下样例，我们发现“在节点 t 被移除之前的每对邻居之间添加一条边”这个操作不改变连通性，因此我们可以考虑将这个操作懒标记掉。

具体来说，对于 s_t=1 的情况，我们可以将其变为“将节点 t 假装删除”，使得它依旧维持着连通性，但是不计入答案。

我们现在要处理的操作是删除节点和假装删除节点。由于都是删除类操作，我们将时间逆序，变为加入。

此时，我们的操作变成了将假装删除的点添加回来和添加一个节点。

这个问题显然可以使用并查集来维护。

细节部分

在并查集中，我们重新定义“大小”这个概念，不是指并查集中有多少个点，而是指并查集中有多少个没有被虚假删除的点，这样方便统计答案。

接着，我们考虑加入一个节点的时候它的哪些邻边应该被加入。这当然是当对面的节点已经被加入以后。

具体的，加入节点 u 的时候，对于他的一条邻边 u\harr v，这条边被加入当且仅当 v 此时已经在图里。这包含两种情况：要么 v>u，要么 s_v=1 （v 只是被虚假删除了）。这样我们就不能按秩合并了，但是加上路径压缩，我们依然能够保证时间复杂度在 O(m \log n) 级别，能够通过本题。

概括

总结一下，我们并查集初始每个点是一个集合，但是“大小”为 0。接着，倒序遍历每个点，对于他的所有邻边，如果对面的点比自己编号大或者属于虚假删除的点，那么加上这条边。最后，将这个点所在的并查集大小加 1。在这个期间维护答案。

\color{Red}坑点

  1. 如果两个假装删除的点之间有边，那么在开始计算之间就应该加上。

    对应的 hack 数据：

    4 3
0011
3 1
1 2
2 4

    正确答案

    6
1
0
0

  2. 十年 OI 一场空，不开 long long 见祖宗！

代码时间

本人比较懒，没有加注释，凑合看吧。

代码曾经有防 CTJ。

#include<iostream>
#include<vector>
using namespace std;
int n,m,fa[200005],sz[200005];
long long sum,ans[200005];
vector<int> g[200005];
bool s[200005];
int get(int u){return (u==fa[u])?u:(fa[u]=get(fa[u]));}
void c(int u,int v)
{
    if(get(u)!=get(v))
        u=fa[u],v=fa[v],
        fa[u]=v,
        sum+=(1ll*sz[u]*sz[v]),
        sz[v]+=sz[u]; 
}
void add(int u)
{
    u=get(u);
    sum+=sz[u];
    sz[u]++;
}
int main()
{
    cin>>n>>m;
    char ch;
    for(int i=1;i<=n;i++)
        fa[i]=i,sz[i]=0;
    for(int i=1;i<=n;i++)
        cin>>ch,s[i]=(ch=='1');
    for(int i=1,u,v;i<=m;i++)
    {
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        if(s[u] && s[v])
            c(u,v);
    }
    for(int i=n;i>=1;i--)
    {
        for(int j:g[i])
            if(j>i || s[j]==1)
                c(i,j);
        add(i);
        ans[i]=sum;
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
}

吐槽

那句 “十年 OI 一场空，不开 long long 见祖宗” 由于一开始试图使用 \Huge + \texttt 表示强调，并且忘了加空格，被打回了 4 次，悲

上面这句吐槽因为一开始滥用代码块又被打回了一次，悲