P8819 [CSP-S 2022] 星战
Tag：图论、哈希
题目描述
在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。
战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：
- 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
- 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。
注意：摧毁只会导致虫洞不可用，而不会消除它的存在。
为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：
- A 型特种部队则可以将某个特定的虫洞修复。
- B 型特种部队可以将某据点的所有损坏的虫洞修复。
考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。
我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。
为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：
- 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
- 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
- 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。
总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。
对于所有数据保证：\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。
| 测试点 | \(n \le\) | \(m \le\) | \(q \le\) | 特殊限制 |
|---|---|---|---|---|
| \(1 \sim 3\) | \(10\) | \(20\) | \(50\) | 无 |
| \(4 \sim 8\) | \({10}^3\) | \({10}^4\) | \({10}^3\) | 无 |
| \(9 \sim 10\) | \(5 \times {10}^5\) | \(5 \times {10}^5\) | \(5 \times {10}^5\) | 保证没有 \(t = 2\) 和 \(t = 4\) 的情况 |
| \(11 \sim 12\) | \(5 \times {10}^5\) | \(5 \times {10}^5\) | \(5 \times {10}^5\) | 保证没有 \(t = 4\) 的情况 |
| \(13 \sim 16\) | \({10}^5\) | \(5 \times {10}^5\) | \(5 \times {10}^5\) | 无 |
| \(17 \sim 20\) | \(5 \times {10}^5\) | \(5\times 10^5\) | \(5 \times {10}^5\) | 无 |
分析
我们先来尝试一下简化题意：
给定一个 \(n\) 个点 \(m\) 条边的有向图，每一条边都有「激活」和「失活」两种状态， 初始状态下所有状态都是激活的。
现在我们有四种操作：
- 失活某条指定的边
- 指定某个点，失活所有以其为终点的边
- 激活某条指定的边
- 指定某个点，激活所有以其为终点的边
之后我们只关注已经被激活的边，看是否满足以下条件：
- 所有点的出度都是 \(1\)
- 所有的点都满足，从这个点出发可以走到一个环中
现在给定若干次操作，要求每次操作之后都判断一次是否满足条件。
首先我们来分析要满足的条件这一部分，第一个条件是所有点的出度都是 \(1\)。
如果一个图的所有点出度都是 \(1\) 的话，那么这个图会组成一个基环内向树森林， 一个基环内向树森林由若干个弱连通块组成，并且每一个弱连通块的本质都是一个基环内向树。 而基环内向树，其性质是从任意一个点出发，都可以走到环上。
因此其实两个条件是互为充要条件的。那么我们其实只需要维护每一个点的出度就可以了。
于是操作 \(1\) 和 \(3\)，我们都可以在常数级复杂度的时间内维护出来， 问题是对于操作 \(2\) 和 \(4\)，我们每一次修改，都需要线性的复杂度。 这样一来我们的做法复杂度为 \(O(nq)\)，但是有两个 \(\text{subtask}\) 保证了没有操作 \(2\) 和操作 \(4\)， 那么这两个测试点里，我们的复杂度就是常数级的。
理论上来说这个做法可以拿到 \(50\) 分，但是由于评测机效率原因，赛事数据稍微卡一下可以拿 \(80\) 分。
显然暴力做法的瓶颈在于操作 \(2\) 和操作 \(4\) 的线性修改复杂度。
如果我们进一步思考这个问题，我们会发现，比起维护出度，貌似站在入度角度思考更加简单。
对于操作 \(2\) 而言，其操作本质就是把某个点的入度变成 \(0\)， 而对于操作 \(4\)，其本质就是把一个点的入度变成其最大值， 而这个最大值是很好维护的。 这样一来我们对于入度的维护可以全部在常数级时间复杂度下完成。
但是有一个很严重的问题，就是对于一个图而言， 一条边确实会贡献一个入度和一个出度，所以一个图的出度和入度总是相等的。 但是总入度为 \(n\)，能说明每个点的入度都是 \(1\) 吗？ 显然不可以。
所以总入度为 \(n\) 只是每一个点出度为 \(1\) 的必要条件， 但是我们可以使用和哈希（\(\text{Sum Hash}\)）使得这个充分性大概率是正确的。
我们对每个点随机生成一个权值 \(w_i\)， 当一个点连出去一条边时，才会贡献出一个 \(w_i\)。 例如上图中的贡献是 \(2\times w_1 + w_3\)， 显然只有当贡献为 \(w_1 + w_2 + w_3\) 的时候才可能满足每个点出度都是 \(1\) 的条件。
图中的总贡献为 \(\displaystyle \sum_{i=1}^n k_i \times w_i\)，\(k_i\) 表示每个点的出度。
现在我们需要满足 \(\sum_{i=1}^n k_i \times w_i = w_i\)，显然只有 \(k_i\) 全部为 \(1\) 时才成立。
这个做法是严格完全正确的吗？显然并非，但是我们把权值在一个足够大的范围内随机映射一个数字，其错误概率会非常小， 甚至小到我们可以不考虑。
基本上全部的随机化题目，都是建立在把错误概率降低到可以不考虑的程度来做的。
在具体的实现中，我们需要给每一个点先随机一个权值 \(\text{val}_i\)。 之后记录 \(\text{tar} = \sum_{i=1}^n val_i\)，\(tar\) 即正确情况下权值和。
我们维护 \(\text{now}_i\) 和 \(\text{sum}_i\)，前者代表目前所有指向点 \(i\) 的点的权值和，后者代表在全部激活的情况下，被贡献到这个点的权值和。
于是每当我们有一条边 \(u \to v\)，我们就可以让 \(\text{now}_v += \text{val}_u\) 同时 \(\text{sum}_v = \text{now}_v\)。
动态维护 \(\text{cur}\) 记录当前状态下权值和， 每次操作之后判断 \(\text{cur}\) 和 \(\text{tar}\) 是否相等即可。
于是我们可以 \(O(1)\) 处理所有的操作。
代码实现
暴力做法
typedef pair<int, int> PII;
void solve() {
int n, m; cin >> n >> m;
vector<int> out(n + 1);
vector<vector<PII>> adj(n + 1);
while (m--) {
int u, v; cin >> u >> v;
out[u]++;
//second代表边是否可用
adj[v].push_back({u, 1});
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (out[i] == 1) {
++cnt;
}
}
int q; cin >> q;
while (q--) {
int op; cin >> op;
if (op == 1) {
int u, v; cin >> u >> v;
if (out[u] == 1) cnt--;
out[u]--;
if (out[u] == 1) cnt++;
for (auto &e: adj[v]) if (e.first == u) e.second = 0;
} else if (op == 3) {
int u, v; cin >> u >> v;
if (out[u] == 1) cnt--;
out[u]++;
if (out[u] == 1) cnt++;
for (auto &e: adj[v]) if (e.first == u) e.second = 1;
} else if (op == 2) {
int cur; cin >> cur;
for (auto &nxt: adj[cur]) {
if (nxt.second == 0) continue;
nxt.second = 0;
int tmp = nxt.first;
if (out[tmp] == 1) cnt--;
out[tmp]--;
if (out[tmp] == 1) cnt++;
}
} else if (op == 4) {
int cur; cin >> cur;
for (auto &nxt: adj[cur]) {
if (nxt.second == 1) continue;
nxt.second = 1;
int tmp = nxt.first;
if (out[tmp] == 1) cnt--;
out[tmp]++;
if (out[tmp] == 1) cnt++;
}
}
if (cnt == n) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
}
void solve() {
int n,m; cin >> n >> m;
srand(time(0));
vector<int> val(n + 1),now(n + 1);
vector<int> sum(n + 1);
for (int u = 1; u <= n; ++u) val[u] = rand();
int tar = 0;
for (int i = 1; i <= n ; ++i) {
tar += val[i];
}
int cur = 0;
while (m--) {
int u,v; cin >> u >> v;
now[v] += val[u];
sum[v] = now[v];
cur += val[u];
}
int q; cin >> q;
while (q--) {
int t;cin >> t;
if (t == 1) {
int u,v; cin >> u >> v;
now[v] -= val[u];
cur -= val[u];
} else if (t == 2) {
int v; cin >> v;
cur -= now[v];
now[v] = 0;
} else if (t == 3) {
int u,v; cin >> u >> v;
now[v] += val[u];
cur += val[u];
} else if (t == 4) {
int v; cin >> v;
cur += sum[v] - now[v];
now[v] = sum[v];
}
if(cur == tar) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
日志
本页面创建于 2025/12/26 17:00