题解：P11674 [USACO25JAN] Reachable Pairs G

MPLN · 2025-01-27 14:28:06 · 题解

部分分思路

，则从图中移除结点 t
如果 s_t=1 ，则从图中移除结点 t ，并在结点 t 被移除之前的每对邻居之间添加一条边

观察题目，这意思不就是如果 s_t=1 ，移除 t 不可能分裂所在集合，没啥影响！设 t 的祖宗是 ft ，移除后只需要让 ans 减去 (size[ft]-1) （ t 可以到的点数量）就可以了。

再考虑 s_i=0 的情况。正难则反，倒着加点可以很轻松地维护：每次加点时一条条连接本来有的边，过程中用乘法原理给被连起来的不同集合中的节点组对，然后增加答案。

至此，我们成功拿到了所有部分分，大概占 50%，是不是很水。

正解

其实正解就是整合一下 s_i=1 和 s_i=0 的方法。但是一个正着走一个反着走，怎么放一起？倒着加点显然更好。

初始化

最初让图中只有节点，没有边。

对于节点 i，若 s_i=1 ，可以在最开始赋予 i 一个状态：“仅连接” （此时已经被删除），保留节点和与其他 “仅连接” 点的相连边。集合中的其他点仍然通过 i 相连，但是不能和 i 组对。

为了方便，我们相对应地给被删除之后的 s_i=0 的节点赋予状态 “删除” ，仅保留单个点，相连边不存在。

由于只能统计 非(“仅连接”或”删除“)状态节点 的答案。不妨称其为 "激活" 节点。因此我们可以改变原本代表集合大小的 size 数组的意义，这里改名为 alive ：alive[i] 表示 i 统治的集合中有多少个 “激活” 节点，只有“激活”节点才会在计算过程中计入答案，否则只是连接作用。

遍历

我们每遍历到一个节点 i ，就需要往图中加入该点原本边集中的边：连接 i 和非同集的 “仅连接” 或 “激活” 节点（其实就是合并集合）。过程中根据两个集合的 alive[i] 增加答案。最后取消 i 的“仅连接”或“删除”状态，再激活 i 即可。

于是我们可以写出代码：加入节点!

void cnct(int x) { // 连边
    no[x] = ny[x] = 0; // 状态清除，不再是“删除”或“仅连接”状态
    int fx = find(x);
    for (int v : e[x]) {
        if (no[v]) continue;  // 如果v是“删除”状态，跳过（不能通过这个节点走）
        int fv = find(v);
        if (fv == fx) continue; // 同一组的不需要再合并
        ans += alive[fv] * alive[fx]; // 乘法原理连接不同集合节点
        fa[fv] = fx;  // 合并两组
        alive[fx] += alive[fv];  // 增加本集合的激活节点数量
    }
    ans += alive[fx]; // 点x连接到自己所在集合内的所有激活节点
    alive[fx]++; // 激活节点x
}

Code

时间复杂度约为 O(n+m) ，空间复杂度 O(n)
赛场代码改了改，加上注释，应该很好理解。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, fa[200010], alive[200010],ans = 0, output[200010];
bool c[200010], no[200010], ny[200010];
char a[200010];
vector<int> e[200010];
int find(int x) { return fa[x] = (fa[x] == x) ? x : find(fa[x]); }
void cnct(int x) { // 连边
    no[x] = ny[x] = 0; // 状态清除，不再是“删除”或“仅连接”状态
    int fx = find(x);
    for (int v : e[x]) {
        if (no[v]) continue;  // 如果v是“删除”状态，跳过（不能通过这个节点走）
        int fv = find(v);
        if (fv == fx) continue; // 同一组的不需要再合并
        ans += alive[fv] * alive[fx]; // 乘法原理连接不同集合节点
        fa[fv] = fx;  // 合并两组
        alive[fx] += alive[fv];  // 增加本集合的激活节点数量
    }
    ans += alive[fx]; // 点x连接到自己所在集合内的所有激活节点
}
signed main() {
    cin >> n >> m;
    scanf("%s", a + 1);
    for (int i = 1; i <= n; i++) {
        c[i] = a[i] == '1';
        fa[i] = i;
        alive[i] = 0;  // 初始没有激活
        if (c[i]) ny[i] = 1;  // 如果c[i]为1，为“仅连接”状态
        else no[i] = 1;  // 否则为“删除”状态
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) if (ny[i]) cnct(i); // 预合并
    // 反向遍历
    for (int i = n; i >= 1; i--) {
        if (c[i]) {
            cnct(i);     // 合并
            alive[find(i)]++; // 激活
        } else {
            cnct(i);     // 合并
            alive[find(i)]++; // 激活
        }
        output[i] = ans;
    }
    for (int i = 1; i <= n; i++) 
        cout << output[i] << endl;
    return 0;
}

第一次进金组还切题了，开心