题解：P8819 [CSP-S 2022] 星战

你说的对，但是，

“不可以，总司令！”

这是一个神秘 trick，它的模板题是 P3560，可以先把这个题写了或者先把星战写了再写模板。

题意简述

题目链接

给出 \(n\) 个点 \(m\) 条边的有向图，每条边有被激活和失活两个状态，有如下四个操作：

1. 使一条边失活；
2. 使一个点的所有入边失活，但是不影响出边；
3. 激活一条边；
4. 激活一个点的所有入边。

每次操作后，对于所有被激活的边，要求判断是否满足以下条件：

• 所有点的入度出度都为 \(1\)；
• 从任意一点出发肯定能走到一个环里。

思路

注意到这是一个向内指的基环树森林，所有点的出度均为 \(1\)，因此我们不需要判环。

又注意到在符合条件的图上，每个点只有一个出度，也就是说这张图上的所有入度中有且只有一个贡献来自于这个点，同时又因为入度等于出度，所以我们记录这张图上所有的入度点是否包含所有的点且每个点只出现一次即可。

现在我们的思路从一开始的维护出度转换为维护入度，现在考虑如何快速维护它。

如果你已经通过了上面的模板题那么你现在就会做了，没写也没关系，我们简单介绍一下。

---

和哈希

考虑哈希维护。我们初始给每一个点都随机一个权值 \(w(x)\)。我们定义一个点 \(v\) 对应的 \(in(v)\) 表示所有直接连向 \(v\) 的点 \(u\) 的 \(w(u)\) 之和，即：

\[in(v) = \sum_{(u, v) \in E} w(u) \]

我们设 \(g(u)\) 表示初始所有边都被激活时的 \(in(v)\) 的值并不再进行修改。（注下面的代码中 in_s[u] 表示 \(g(u)\)）

现在重新设计四个操作：

1. \(in(v) \leftarrow in(v) - w(u)\)；
2. \(in(v) \leftarrow 0\)；
3. \(in(v) \leftarrow in(v) + w(u)\)；
4. \(in(v) \leftarrow g(v)\)。

于是我们现在就可以 \(O(1)\) 维护这四个操作，同时也能 \(O(1)\) 维护当前所有点的 \(in\) 之和。

考虑如何判断答案，我们可以实现求出来所有点的权值 \(\sum w(u)\)，当 \(\sum in(u) = \sum w(u)\) 时是符合题意的，原因我们上面已经介绍了。

但是这种写法本质上是哈希，那么如何保证正确性？

我们假设在每一个 \(w(u)\) 前加一个系数 \(k(u)\)，上面的情况可以转化为 \(\sum in(u) = \sum k(u) \times w(u)\) 即 \(\sum w(u) = \sum k(u) \times w(u)\)，此时当所有 \(k(u) = 1\) 肯定是一个合法的解，我们就是把这个作为判断条件。

但是有没有其它解呢？固然是是有的。但是你的权值是随机生成的，被卡掉的概率极小，所以这么写的正确性还是有保障的。

引用题解的一句话：

这就是哈希的原理了：判定时构造一个必要不充分条件，但这个“不充分”实际上有非常大非常大的概率充分，以至于不充分性可以忽略不计，从而达到充要判定的效果。读者应当熟悉的字符串哈希，也是同样的原理。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;const int MN = 5e5 + 3, mod = 1e9 + 123;
int n, m, q;
int h[MN], acc, in[MN], in_s[MN], cur;bool solve() {int op, x, y;cin >> op;if (op == 1) {cin >> x >> y;in[y] = ((in[y] - h[x]) % mod + mod) % mod;cur = ((cur - h[x]) % mod + mod) % mod;}else if (op == 2) {cin >> x;cur = ((cur - in[x]) % mod + mod) % mod;in[x] = 0;}else if (op == 3) {cin >> x >> y;in[y] = (in[y] + h[x]) % mod;cur = (cur + h[x]) % mod;}else if (op == 4) {cin >> x;int tmp = ((in_s[x] - in[x]) % mod + mod) % mod;in[x]= in_s[x];cur = (cur + tmp) % mod;}return cur == acc;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);srand(time(0));cin >> n >> m;for (int i = 1; i <= n; i++) h[i] = rand() % mod, acc = (h[i] + acc) % mod;for (int i = 1, x, y; i <= m; i++) {cin >> x >> y;in[y] = (in[y] + h[x]) % mod;in_s[y] = in[y];cur = (cur + h[x]) % mod;}cin >> q;while (q--) {if (solve()) cout << "YES\n";else cout << "NO\n";}return 0;
}

碎碎念 & 参考文章

除了这个 trick 本身，我还是觉得这个题的转化很有意思，所以虽然 CSP-S 考完了但还是写了还是我写题太少了你有意见就是你对。

参考：https://www.luogu.com.cn/article/63vl9zh2

有用就点个赞吧 QAQ。