[CSP-S 2022] 星战

GitHub 跳转原题关系图返回列表

把每条可用边贡献为源点随机权值，维护全图哈希和判断是否所有点出度为 1。

OJ: luogu

题目 ID: P8819

难度:提高+/省选-

标签:图论哈希模拟

日期: 2026-07-06 08:46

题意

给定一张有向图，初始所有边都可用。每次操作会删除或恢复一条边，或者删除、恢复某个点的所有入边。每次操作后，需要判断当前是否是一个可以反攻的时刻。

题目中的两个条件合起来，可以转化为一个很简洁的图论条件：每个点当前恰好有一条可用出边。

如果每个点出度都是 1，那么从任意点出发，每一步都能沿唯一出边继续走。图是有限的，所以一定会进入环，从而可以无限穿梭。反过来，如果某个点出度不是 1，它就不满足“恰好一条可用虫洞”的连续穿梭条件。

思路

小数据可以直接维护每条边是否可用，每次操作后重新统计所有点出度：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74// brute.cpp：小数据暴力解，直接维护每条边是否可用并检查每个点当前出度。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, m, q;
bool exist_edge[MAXN][MAXN];
bool active_edge[MAXN][MAXN];

bool can_counterattack() {
    for (int u = 1; u <= n; u++) {
        int out_degree = 0;
        for (int v = 1; v <= n; v++) {
            if (active_edge[u][v]) {
                out_degree++;
            }
        }
        if (out_degree != 1) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        exist_edge[u][v] = true;
        active_edge[u][v] = true;
    }

    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            active_edge[u][v] = false;
        } else if (type == 2) {
            int v;
            cin >> v;
            for (int u = 1; u <= n; u++) {
                if (exist_edge[u][v]) {
                    active_edge[u][v] = false;
                }
            }
        } else if (type == 3) {
            int u, v;
            cin >> u >> v;
            if (exist_edge[u][v]) {
                active_edge[u][v] = true;
            }
        } else {
            int v;
            cin >> v;
            for (int u = 1; u <= n; u++) {
                if (exist_edge[u][v]) {
                    active_edge[u][v] = true;
                }
            }
        }

        cout << (can_counterattack() ? "YES" : "NO") << '\n';
    }

    return 0;
}

暴力的瓶颈在于：n,m,q 都可以达到 5 * 10^5，而“删除某点所有入边”会影响很多源点的出度，不能每次暴力扫描。

我们给每个点 u 一个固定的 64 位权值 w[u]。一条当前可用边 u -> v 对全局贡献 w[u]。于是全图当前贡献为：

text

1current = sum(w[u] * 当前 u 的出度)

如果每个点出度都恰好为 1，那么：

text

1current = sum(w[u])

这就是目标值 target。

为了快速处理“按终点删除/恢复所有入边”，再维护两个数组：

full_in_sum[v]：原图中所有终点为 v 的边贡献和；
cur_in_sum[v]：当前仍可用、且终点为 v 的边贡献和。

操作就变成：

删除单边 u -> v：cur_in_sum[v] -= w[u]，current -= w[u]；
恢复单边 u -> v：对应加回；
删除所有入边到 v：从 current 中减去 cur_in_sum[v]，再把它清零；
恢复所有入边到 v：把 cur_in_sum[v] 恢复成 full_in_sum[v]，并补上差值。

每次操作后判断 current == target，即可得到答案。这里使用 64 位哈希，发生碰撞的概率极低；竞赛中这种随机哈希维护集合/计数状态是常见写法。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73// main.cpp：用源点随机权值的哈希和维护“每个点出度是否都为 1”。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int n, m, q;
unsigned long long value_of_node[MAXN];
unsigned long long full_in_sum[MAXN]; // 终点为 v 的所有原始边的源点权值和
unsigned long long cur_in_sum[MAXN];  // 终点为 v 的当前可用边的源点权值和
unsigned long long target_sum;
unsigned long long current_sum;

unsigned long long splitmix64(unsigned long long x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        value_of_node[i] = splitmix64((unsigned long long)i);
        target_sum += value_of_node[i];
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        full_in_sum[v] += value_of_node[u];
        cur_in_sum[v] += value_of_node[u];
        current_sum += value_of_node[u];
    }

    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            cur_in_sum[v] -= value_of_node[u];
            current_sum -= value_of_node[u];
        } else if (type == 2) {
            int v;
            cin >> v;
            current_sum -= cur_in_sum[v];
            cur_in_sum[v] = 0;
        } else if (type == 3) {
            int u, v;
            cin >> u >> v;
            cur_in_sum[v] += value_of_node[u];
            current_sum += value_of_node[u];
        } else {
            int v;
            cin >> v;
            current_sum += full_in_sum[v] - cur_in_sum[v];
            cur_in_sum[v] = full_in_sum[v];
        }

        if (current_sum == target_sum) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

复杂度

初始化需要读入所有边，复杂度 $O(n + m)$ 。

每次操作只做常数次加减，时间复杂度 $O(1)$ 。总时间复杂度为 $O(n + m + q)$ ，空间复杂度为 $O(n)$ 。

总结

本题难点是把复杂题意压缩成“每个点当前出度恰好为 1”。真正的优化点在于：不要维护每个出度的精确修改过程，而是用源点权值的全局贡献和来代表所有出度状态。

当操作天然按“终点的所有入边”成组变化时，维护每个终点的当前入边贡献和，就能把批量修改降成一次加减。

P8819 [CSP-S 2022] 星战

题目描述

在这一轮的星际战争中，我方在宇宙中建立了 $n$ 个据点，以 $m$ 个单向虫洞连接。我们把终点为据点 $u$ 的所有虫洞归为据点 $u$ 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

A 型特种部队则可以将某个特定的虫洞修复。
B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。

输入格式

输入的第一行包含两个正整数 $n,m$ 。

接下来 $m$ 行每行两个数 $u,v$ ，表示一个从据点 $u$ 出发到据点 $v$ 的虫洞。保证 $u \ne v$ ，保证不会有两条相同的虫洞。初始时所有的虫洞和据点都是完好的。

接下来一行一个正整数 $q$ 表示询问个数。

接下来 $q$ 行每行表示一次询问或操作。首先读入一个正整数 $t$ 表示指令类型：

若 $t = 1$ ，接下来两个整数 $u, v$ 表示敌人摧毁了从据点 $u$ 出发到据点 $v$ 的虫洞。保证该虫洞存在且未被摧毁。
若 $t = 2$ ，接下来一个整数 $u$ 表示敌人摧毁了据点 $u$ 。如果该据点的虫洞已全部被摧毁，那么这次袭击不会有任何效果。
若 $t = 3$ ，接下来两个整数 $u, v$ 表示我方修复了从据点 $u$ 出发到据点 $v$ 的虫洞。保证该虫洞存在且被摧毁。
若 $t = 4$ ，接下来一个整数 $u$ 表示我方修复了据点 $u$ 。如果该据点没有被摧毁的虫洞，那么这次修复不会有任何效果。

在每次指令执行之后，你需要判断能否进行一次反攻。如果能则输出 YES 否则输出 NO。

输出格式

输出一共 $q$ 行。对于每个指令，输出这个指令执行后能否进行反攻。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
3
4
5
6
7
8
9
10
11NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO

说明/提示

【样例解释 #1】

虫洞状态可以参考下面的图片, 图中的边表示存在且未被摧毁的虫洞：

【样例 #2】

见附件中的 galaxy/galaxy2.in 与 galaxy/galaxy2.ans。

【样例 #3】

见附件中的 galaxy/galaxy3.in 与 galaxy/galaxy3.ans。

【样例 #4】

见附件中的 galaxy/galaxy4.in 与 galaxy/galaxy4.ans。

【数据范围】

对于所有数据保证： $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$	无

[CSP-S 2022] 星战

目录

题意

思路

代码

复杂度

总结