「一本通 3.5 练习 3」间谍网络

形式化题目

给定 $n$ 个点的有向图，边 $A \to B$ 表示逮捕 $A$ 后获得其情报、可继续逮捕 $B$ ，控制沿有向路径传递。其中 $p$ 个点各带一个非负收买金额，收买等价于把该点作为零成本的初始入口。

求费用最小的收买集合，使其出发沿有向边可达全部点；若不存在这样的集合，输出任何收买方案都到达不了的点中编号最小者。

样例说明

样例的边为 $1 \to 2$ 、 $2 \to 1$ ，只有间谍 2 可收买（金额 512）。下图按互相可达关系分组： $1$ 与 $2$ 同属一个强连通分量。

graph LR
    subgraph C1["强连通分量 {1, 2}"]
        n1["1"] --> n2["2"]
        n2 --> n1
    end

两个点互相可达，控制其中一个即控制另一个；分量内唯一的可收买者是 2，收买他即控制全场，故输出 YES / 512。

正解

思路

朴素做法与瓶颈。 直观做法是把"控制"当传递闭包算：从每个可收买点各 BFS 一遍（或用 Floyd 求可达矩阵），统计能到达的点。而"哪些点必须自己收买"想在原图上用入度判断——入度为 0 的点没人能到达，只能买。这里有两个瓶颈：① 环会让入度判断概念性失效：互相指向的环上每点都有入边，看起来"会被别人控制"，实际环外无人能到时，环内一个都控制不了；② 可达性记录需要 $O(n^2)$ 空间， $n = 3000$ 时约 $9 \times 10^6$ 项，Python 下不可接受。

缩点：把环压成点。 互相可达是等价关系：若 $u \leftrightarrow v$ ，则任意 $w$ 能到达 $u$ 当且仅当能到达 $v$ 。因此"能否被控制"在强连通分量内完全一致，把每个 SCC 缩成一个点后得到 DAG（若缩点后仍有环，环上各点本应属同一分量）。收买分量内任一成员即可控制全分量，所以每个分量只需回答两件事：分量内最低可收买金额是多少、缩点后入度是否为 $0$ 。

源点判定与最优花费。 缩点 DAG 中入度为 $0$ 的分量没有任何外界能到达，要控制它只能收买其内部成员——源点必须买；另一方面，DAG 中任一分量沿入边逆推必然终止在某个源点分量，所以买齐所有源点分量即可覆盖全图，不多不少。于是：

有解 $\iff$ 每个源点分量内至少有一个可收买者；
最小花费 $=$ 各源点分量最低价之和（源点一个不能少，非源点全被覆盖，无需多买）。

样例缩点后只有分量 $\{1, 2}$ 这一个源点，最低价 512，即答案。

无解输出的坑。 NO 的答案是"任何方案都控制不到的点"的最小编号。死源点（入度 0 且不可收买）的成员一定不可控，但死源点下游、且不被任何可收买分量到达的点同样不可控，编号可能更小。正确做法：从所有含可收买者的分量出发在 DAG 上做可达性标记——收买者只能买可收买分量内的点，任一方案的控制范围都不超过这个并集，而买下全部可收买分量恰好达到它——未被标记的分量即全不可控集，取 min(分量内最小编号)。下图是无解的最小例子：可收买者只有 4，分量 $\{3\}$ 是死源点，点 1、2 只被 $\{3\}$ 可达，点 4 只控制自己：

graph LR
    c3["分量 {3}：入度 0 且不可收买"] --> c1["分量 {1}"]
    c3 --> c2["分量 {2}"]
    c4["分量 {4}：入度 0，可收买 10"]

不可控集是 $\{1, 2, 3\}$ ，答案为 $1$ ——若只取死源点 $\{3\}$ 的成员会误答 $3$ 。存在死源点时这个补集必非空，补集为空时所有源点又都能被收买，所以代码直接用补集是否为空判定有解，两个条件是等价的。

实现要点。 $n = 3000$ 超过 Python 默认递归上限，Tarjan 用显式栈写成迭代：栈元素为「当前点 + 下一条待走的边」，一个点的全部出边走完才判根弹分量。读入用单一整数迭代器，边表只扫两遍（建缩点图 + 建入度）。

代码

Python 版：

python

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 15:44
# update_at: 2026-09-30 15:44

import sys

INF = 10**9  # 分量代价初值：尚未发现可收买成员


def scc(n: int, g: list[list[int]]) -> list[int]:
    """Tarjan 强连通分量（迭代版）：返回 comp[v]，同一分量内的点互相可达。"""
    num = [0] * (n + 1)        # DFS 编号，0 表示未访问
    low = [0] * (n + 1)        # 子树里的点能回到的最小编号
    on_st = [False] * (n + 1)  # 是否在栈上（仍是当前分量的候选）
    st: list[int] = []
    comp = [-1] * (n + 1)
    frame: list[tuple[int, int]] = []  # 显式栈：(点, 下一条待走的边)，替代递归
    seq = 0      # 全局 DFS 时钟
    comp_id = 0  # 已确定的分量编号

    for root in range(1, n + 1):
        if num[root]:
            continue
        seq += 1
        num[root] = low[root] = seq
        st.append(root)
        on_st[root] = True
        frame.append((root, 0))
        while frame:
            v, ei = frame[-1]
            if ei < len(g[v]):  # 还有边没走
                frame[-1] = (v, ei + 1)
                w = g[v][ei]
                if not num[w]:  # 树边：深入
                    seq += 1
                    num[w] = low[w] = seq
                    st.append(w)
                    on_st[w] = True
                    frame.append((w, 0))
                elif on_st[w]:  # 回边：v 能经 w 回到更早的点
                    low[v] = min(low[v], num[w])
            else:  # v 的边走完，弹栈定根
                frame.pop()
                if low[v] == num[v]:  # 没有出路指回外面 → 整个栈顶段是一个分量
                    while (w := st.pop()):  # 弹到 v 为止（点编号 ≥ 1，0 不会入栈）
                        on_st[w] = False
                        comp[w] = comp_id
                        if w == v:
                            break
                    comp_id += 1
    return comp


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)            # 间谍总数
    p = next(data)            # 可收买人数
    bribe = {next(data): next(data) for _ in range(p)}  # 编号 -> 收买金额
    r = next(data)            # 证据条数
    edges = [(next(data), next(data)) for _ in range(r)]  # (A, B)：A 掌握 B 的证据

    g: list[list[int]] = [[] for _ in range(n + 1)]
    for a, b in edges:
        g[a].append(b)        # 逮捕 A 即控制 B → 有向边 A -> B

    comp = scc(n, g)
    k = max(comp[1:]) + 1                # 强连通分量个数
    head = [n + 1] * k                   # 每个分量里最小的间谍编号
    for v in range(1, n + 1):
        cv = comp[v]
        head[cv] = min(head[cv], v)
    cost = [INF] * k                     # 分量内可收买成员的最低金额
    for spy, money in bribe.items():
        cv = comp[spy]
        cost[cv] = min(cost[cv], money)

    cond: list[list[int]] = [[] for _ in range(k)]  # 缩点后的 DAG
    indeg = [0] * k
    for a, b in edges:
        ca, cb = comp[a], comp[b]
        if ca != cb:
            cond[ca].append(cb)
            indeg[cb] += 1

    # 从每个可收买分量出发做可达性标记：能被控制的分量
    ctrl = [False] * k
    stack = [c for c in range(k) if cost[c] < INF]
    for c in stack:
        ctrl[c] = True
    while stack:
        c = stack.pop()
        for nb in cond[c]:
            if not ctrl[nb]:
                ctrl[nb] = True
                stack.append(nb)

    # 入度 0 的分量没有任何外界能到达，必须自己收买；买下它们即可覆盖全图
    source = [c for c in range(k) if indeg[c] == 0]
    lost = [c for c in range(k) if not ctrl[c]]  # 任何收买方案都控制不到的分量

    if lost:
        out = ['NO', str(min(head[c] for c in lost))]
    else:
        out = ['YES', str(sum(cost[c] for c in source))]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:50
 * update_at: 2026-10-05 05:50
 */
// 1517 间谍网络：Tarjan 缩点成 DAG，源点分量必须收买、买齐即全控；
// 无解时从可收买分量出发做可达性标记，取不可控分量的最小编号。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;
const int MAXM = 8005;

typedef long long ll;

const ll INF = 1e18;

ll n, p, r;
ll ea[MAXM], eb[MAXM];      // 证据对 (A, B)：逮捕 A 后可继续逮捕 B，即有向边 A -> B
ll bribe_cost[MAXN];        // bribe_cost[i] = 间谍 i 的收买金额，不可收买为 INF

// 原图邻接表（链式前向星）
int head[MAXN], nxt[MAXM], to[MAXM], edge_cnt;

// Tarjan 所需
ll dfn[MAXN], low[MAXN];
bool on_st[MAXN];
int stk[MAXN], top_stk;     // Tarjan 的点栈
int comp[MAXN];             // comp[v] = v 所在强连通分量编号
int comp_cnt;

// 缩点后各分量的统计
ll comp_cost[MAXN];         // 分量内可收买成员的最低金额，INF 表示不可收买
ll comp_min_id[MAXN];       // 分量内最小的间谍编号
ll indeg[MAXN];             // 缩点后 DAG 的入度

// 缩点后的 DAG（也用链式前向星）
int chead[MAXN], cnxt[MAXM], cto[MAXM], cedge_cnt;

// 加一条原图边 u -> v。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 加一条缩点图边 cu -> cv。
void add_cedge(int cu, int cv) {
    cedge_cnt++;
    cto[cedge_cnt] = cv;
    cnxt[cedge_cnt] = chead[cu];
    chead[cu] = cedge_cnt;
}

// Tarjan 求强连通分量：一个点的出边全部走完后，若 low == dfn 则它是分量根。
void tarjan(int u) {
    static int timer = 0;
    top_stk++;
    stk[top_stk] = u;
    on_st[u] = true;
    timer++;
    dfn[u] = low[u] = timer;

    for (int i = head[u]; i != 0; i = nxt[i]) {
        int v = to[i];
        if (dfn[v] == 0) {          // 树边：深入
            tarjan(v);
            if (low[v] < low[u]) low[u] = low[v];
        } else if (on_st[v]) {      // 回边：u 能经 v 回到更早的点
            if (dfn[v] < low[u]) low[u] = dfn[v];
        }
    }

    if (low[u] == dfn[u]) {         // u 是分量根：弹栈到 u 为止，整段是一个分量
        comp_cnt++;
        while (top_stk > 0) {
            int w = stk[top_stk];
            top_stk--;
            on_st[w] = false;
            comp[w] = comp_cnt;
            if (w == u) break;
        }
    }
}

ll read_input() {
    cin >> n;
    // 不可收买的间谍金额记为 INF，避免全局零初始化被当成 0 元收买
    for (ll i = 1; i <= n; i++) bribe_cost[i] = INF;
    cin >> p;
    for (ll i = 1; i <= p; i++) {
        ll id, money;
        cin >> id >> money;
        bribe_cost[id] = money;
    }
    cin >> r;
    for (ll i = 1; i <= r; i++) {
        cin >> ea[i] >> eb[i];
        add_edge(ea[i], eb[i]);
    }
    return 0;
}

void solve() {
    // 1. 求每个点的强连通分量编号
    for (ll i = 1; i <= n; i++) {
        if (dfn[i] == 0) tarjan(i);
    }

    // 2. 统计每个分量的最低收买金额和最小编号
    for (ll c = 1; c <= comp_cnt; c++) {
        comp_cost[c] = INF;
        comp_min_id[c] = INF;
    }
    for (ll v = 1; v <= n; v++) {
        ll c = comp[v];
        if (v < comp_min_id[c]) comp_min_id[c] = v;
        if (bribe_cost[v] < comp_cost[c]) comp_cost[c] = bribe_cost[v];
    }

    // 3. 建缩点后的 DAG 并统计入度（跨分量的边才计入）
    for (ll i = 1; i <= r; i++) {
        ll ca = comp[ea[i]], cb = comp[eb[i]];
        if (ca != cb) {
            add_cedge(ca, cb);
            indeg[cb]++;
        }
    }

    // 4. 从每个可收买分量出发做可达性标记：
    //    任一收买方案的控制范围都不超过这些分量的可达并集
    static bool ctrl[MAXN];     // ctrl[c] = 分量 c 能否被某个收买方案控制
    static int bfsq[MAXN];
    int qh = 0, qt = 0;
    for (ll c = 1; c <= comp_cnt; c++) {
        if (comp_cost[c] < INF) {
            ctrl[c] = true;
            qt++;
            bfsq[qt] = c;
        }
    }
    while (qh < qt) {
        qh++;
        int c = bfsq[qh];
        for (int i = chead[c]; i != 0; i = cnxt[i]) {
            int v = cto[i];
            if (!ctrl[v]) {
                ctrl[v] = true;
                qt++;
                bfsq[qt] = v;
            }
        }
    }

    // 5. 判定与输出：
    //    无解 <=> 存在不可控分量（此时必有死源点，补集非空，两个条件等价）
    ll lost_min_id = INF;
    for (ll c = 1; c <= comp_cnt; c++) {
        if (!ctrl[c] && comp_min_id[c] < lost_min_id) {
            lost_min_id = comp_min_id[c];
        }
    }
    if (lost_min_id != INF) {
        cout << "NO\n" << lost_min_id << "\n";
        return;
    }

    // 有解：入度 0 的源点分量必须买（没人能到它们），买齐即覆盖全图
    ll ans = 0;
    for (ll c = 1; c <= comp_cnt; c++) {
        if (indeg[c] == 0) ans += comp_cost[c];
    }
    cout << "YES\n" << ans << "\n";
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间 $O(n + r)$ ：Tarjan 每点每边访问常数次，建缩点图与入度、可达性标记各扫一遍边表。与 C++ 正解（Kosaraju / Tarjan 缩点）同阶。
空间 $O(n + r)$ ：邻接表与缩点图各一份，加上若干 $O(n)$ 数组和显式栈。

总结

"收买 → 可达"的控制传播天然是有向图问题；互相指向的环使原图入度失效，而互相可达的等价性恰好允许把图缩成 DAG。缩点后答案坍缩成两句话：源点必须买、买齐即全控，有解时花费就是各源点最低价之和；无解时输出从可收买分量出发不可达的最小编号（注意包含死源点下游）。整题即「Tarjan 缩点 + 源点贪心 + 可达性标记」， $O(n + r)$ 一步到位。

验证：题面样例输出 YES / 512；仓库真实数据 data/net1..12 全部 PASS（verify.sh，12/12，单测例 ≤ 0.05s、峰值 ≤ 20MB，远低于 1000ms / 128MB），含 7 组 NO 用例。