专栏文章

题解：P11674 [USACO25JAN] Reachable Pairs G

MMPLN
P11674题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqdsxgl
此快照首次捕获于
2025/12/04 03:09
3 个月前
此快照最后确认于
2025/12/04 03:09
3 个月前
查看原文

部分分思路

N≤100N\le100 时，考虑每次暴力 DFS ，O(nm)O(nm) 。
认真读题，很容易想到要用并查集维护点的连接情况。
如果 st=0s_t=0 ，则从图中移除结点 tt
如果 st=1s_t=1 ，则从图中移除结点 tt ，并在结点 tt 被移除之前的每对邻居之间添加一条边
观察题目，这意思不就是如果 st=1s_t=1 ，移除 tt 不可能分裂所在集合，没啥影响！设 tt 的祖宗是 ftft ，移除后只需要让 ansans 减去 (size[ft]−1)(size[ft]-1) （ tt 可以到的点数量）就可以了。
再考虑 si=0s_i=0 的情况。正难则反，倒着加点可以很轻松地维护：每次加点时一条条连接本来有的边，过程中用乘法原理给被连起来的不同集合中的节点组对，然后增加答案。
至此，我们成功拿到了所有部分分，大概占 50%，是不是很水。

正解

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

初始化

最初让图中只有节点，没有边。
对于节点 ii，若 si=1s_i=1 ，可以在最开始赋予 ii 一个状态：“仅连接” （此时已经被删除），保留节点和与其他 “仅连接” 点的相连边。集合中的其他点仍然通过 ii 相连，但是不能和 ii 组对。
为了方便，我们相对应地给被删除之后的 si=0s_i=0 的节点赋予状态 “删除” ，仅保留单个点，相连边不存在。
由于只能统计 非(“仅连接”或”删除“)状态节点 的答案。不妨称其为 "激活" 节点。因此我们可以改变原本代表集合大小的 sizesize 数组的意义，这里改名为 alivealive ：alive[i]alive[i] 表示 ii 统治的集合中有多少个 “激活” 节点，只有“激活”节点才会在计算过程中计入答案，否则只是连接作用。

遍历

我们每遍历到一个节点 ii ，就需要往图中加入该点原本边集中的边：连接 ii 和非同集的 “仅连接” 或 “激活” 节点（其实就是合并集合）。过程中根据两个集合的 alive[i]alive[i] 增加答案。最后取消 ii 的“仅连接”或“删除”状态，再激活 ii 即可。
于是我们可以写出代码：加入节点!
CPP
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+m) ，空间复杂度 O(n)O(n)
赛场代码改了改，加上注释，应该很好理解。
CPP
#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;
}
第一次进金组还切题了，开心

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...