[POI 1996 R3] 间谍网络

形式化题目

给定一张有向图， $n$ 个点表示间谍，一条有向边 $A\to B$ 表示 $A$ 掌握 $B$ 的证据。部分点标了价格 $c_v$ ，其余点不可收买。

若收买点集 $S$ ，则定义"被控制"的点集为从 $S$ 出发沿有向边可达的所有点（含 $S$ 自身）。

要求二选一：

若存在 $S$ 使全部 $n$ 个点都被控制，则输出该情形下 $\sum_{v\in S} c_v$ 的最小值；
否则输出所有"无法被控制"的点中编号最小的那个。

注意"控制"是单向传递的： $A$ 被控制后， $A$ 掌握的证据全部到手，于是 $A$ 的直接下游也被控制，以此类推。它不是"每个人各自需要一个监护人"的配对关系。

样例一： $c_1=10$ 、 $c_2=100$ ，边 $1\to3$ 、 $2\to3$ 。买 $1$ 与 $2$ 后 $3$ 顺带被控制，花费 $110$ 。若只买 $1$ ， $2$ 无人能揭发，买不动。

样例二： $c_1=100$ 、 $c_4=200$ ，边 $1\to2$ 、 $3\to4$ 。 $3$ 既不可收买、又没有入边，谁也控制不了它，无解；无法控制的点是 $\{3,4\}$ ，输出编号最小的 $3$ 。

暴力解法

思路

按定义直接枚举决策。方案就是一个可收买者的子集，共 $2^p$ 种（ $p$ 是可收买人数）。

对每个子集，做一次可达性标记：把选中的点全部入队，沿边向外扩散，标记所有能到达的点。扩散结束后检查 $1\sim n$ 是否全部被标记，是则用该子集的花费去更新答案。

用一个 01 序列递归枚举"第 $i$ 个可收买者买不买"，到叶子时统一检查。

无解分支也可以这样得到：买得越多可达范围只会更大，所以"全部买下"就是可达集的上界。全买之后仍未被标记的点，就是永远无法控制的点，取编号最小者输出。

代码

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/**
 * 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-22 21:50
 * update_at: 2026-10-22 21:50
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举所有可收买者的子集。
// 本层在设计"第 dep 个可收买者买不买"，到叶子时判断能否控制全部间谍。
//
// 题意直接建模：买下一个集合 S 后，从 S 出发沿"掌握证据"的有向边能走到的人
// 全部被控制。所以暴力只需枚举 S 的每个子集，做一次可达性标记，检查是否覆盖了
// 所有人，在所有可行子集里取花费最小者。无解时输出买下全部可收买者仍然走不到的人
// 里编号最小的那个（买得越多可达范围只会更大，所以全买就是最大可达集）。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3005;
const int maxm = 8005;
const int INF = 1e9;

int n, p, r;

int buyer[maxn];   // buyer[i] = 第 i 个可收买者（1..p）
int price[maxn];   // price[i] = 收买 buyer[i] 的价格
int cost[maxn];    // cost[v] = 收买 v 的价格，INF 表示不可收买

int eu[maxm], ev[maxm];  // 第 i 条边 eu[i] -> ev[i]

int choose_[maxn];  // choose_[i] = 第 i 个可收买者是否被买下

int best_cost = INF;  // 当前最优总花费

// 从选中的可收买者出发做可达性标记，返回 true 表示全部 n 人都被控制
bool check() {
    static bool reach[maxn];
    static int que[maxn];

    for (int v = 1; v <= n; v++) reach[v] = false;

    int head = 0, tail = 0;
    for (int i = 1; i <= p; i++) {
        if (choose_[i]) {
            int v = buyer[i];
            if (!reach[v]) {
                reach[v] = true;
                que[tail++] = v;
            }
        }
    }

    // 邻接表用邻接矩阵太慢，这里按边表线性扫描（小数据够用）
    while (head < tail) {
        int u = que[head++];
        for (int i = 1; i <= r; i++) {
            if (eu[i] == u && !reach[ev[i]]) {
                reach[ev[i]] = true;
                que[tail++] = ev[i];
            }
        }
    }

    for (int v = 1; v <= n; v++) {
        if (!reach[v]) return false;
    }
    return true;
}

// 这一层在决定"第 dep 个可收买者买不买"
void dfs(int dep, int sum) {
    if (sum >= best_cost) return;  // 剪枝：已经不比当前最优更好

    if (dep > p) {
        if (check()) best_cost = min(best_cost, sum);
        return;
    }

    choose_[dep] = 0;
    dfs(dep + 1, sum);

    choose_[dep] = 1;
    dfs(dep + 1, sum + price[dep]);
    choose_[dep] = 0;
}

void read_input() {
    cin >> n;
    cin >> p;
    fill(cost, cost + n + 1, INF);
    for (int i = 1; i <= p; i++) {
        int v, c;
        cin >> v >> c;
        buyer[i] = v;
        price[i] = c;
        cost[v] = c;
    }
    cin >> r;
    for (int i = 1; i <= r; i++) {
        cin >> eu[i] >> ev[i];
    }
}

void solve() {
    dfs(1, 0);

    if (best_cost < INF) {
        cout << "YES\n" << best_cost << "\n";
        return;
    }

    // 无解：买下所有人仍然控制不到的人，取编号最小
    for (int i = 1; i <= p; i++) choose_[i] = 1;
    check();

    static bool reach[maxn];
    for (int v = 1; v <= n; v++) reach[v] = false;
    static int que[maxn];
    int head = 0, tail = 0;
    for (int i = 1; i <= p; i++) {
        int v = buyer[i];
        if (!reach[v]) { reach[v] = true; que[tail++] = v; }
    }
    while (head < tail) {
        int u = que[head++];
        for (int i = 1; i <= r; i++) {
            if (eu[i] == u && !reach[ev[i]]) {
                reach[ev[i]] = true;
                que[tail++] = ev[i];
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        if (!reach[v]) { cout << "NO\n" << v << "\n"; return; }
    }
}

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

    read_input();
    solve();

    return 0;
}

复杂度

记 $m$ 为边数。每个子集要做一次 $O(n+m)$ 的扩散，总时间 $O(2^p(n+m))$ ，空间 $O(n+m)$ 。 $p$ 最大可等于 $n=3000$ ， $2^{3000}$ 完全不可行，这个做法只能验算很小的数据。

瓶颈

瓶颈不在于"检查一个方案"——那部分只需要一趟 BFS，是线性的、没问题的。

真正的瓶颈是方案数量： $2^p$ 个候选子集。而且这些候选之间并不独立：买了 $A$ 可能顺带控制 $B,C,D$ ，各种选择的效果大量重叠，看起来像集合覆盖那类难以下手的问题。

要降低复杂度，就必须意识到：并不是每个可收买者都值得单独决策。一个点如果能由别人走到，它自己就不必花钱。这句话把"选一个子集"压成了"选几个入口"。下面的正解就是从这一点出发的。

正解

思路

问题一：如果 $A$ 能揭发 $B$ 、 $B$ 又能揭发 $A$ （或绕一圈回到 $A$ ），还需要在环上挑选吗？

不需要。买下环上任意一个有价的人，环上所有人立刻到手，再顺着环上各点的出边扩散，他们的下游也全部到手。所以环内根本不存在选择问题，只需要挑环里最便宜的可收买者。

把"能互相到达"推广成等价关系，就得到强连通分量（SCC）。同一个分量内的点在本题中完全不可区分，只需要保留一个信息：分量内最便宜的可收买价。

问题二：缩点之后，哪些人是非买不可的？

把每个 SCC 缩成一个点，得到一张缩点图。因为分量已经是"极大"的互相可达集合，缩点图里不可能还有环——否则环上那些分量本该合并成一个。所以缩点图是 DAG。

在 DAG 里，考虑入度为 $0$ 的分量：它没有任何跨分量的入边，意味着分量外面没有任何人能走到它里面的人。既然从外部无法进入，就只能直接收买。这是全题唯一被强制的地方。

问题三：只买这些入度为 $0$ 的分量，够了没有？

够了。DAG 有一个基本性质：每个点都从某个入度为 $0$ 的点可达。反证——假设某点 $x$ 从任何入度为 $0$ 的点都到不了，那就从 $x$ 出发沿入边一路往上走；点数有限而 $x$ 的祖先里不存在入度为 $0$ 的点，说明这条上溯路径必然绕回访问过的点，形成环，与 DAG 矛盾。

所以从每个入度为 $0$ 的分量进入一次，整张缩点图都被覆盖，也就是所有间谍都被控制。

必要性与充分性合起来：答案恰好是每个入度为 $0$ 的分量内最便宜可收买价之和。

问题四：什么时候无解？无解时该输出哪个编号？

某个入度为 $0$ 的分量里一个可收买者都没有时无解——它既不能从外部被揭发（入度为 $0$ ），内部又没人买得起。

输出编号这里有一个极易踩的坑：不能输出那个坏分量的最小编号。坏分量一旦失控，它下游的所有人同样失控，而那些下游点的编号可能更小。

正确做法是回到题面定义：从所有可收买点出发做一次可达性标记（买得越多范围越大，全买就是最大可达集），输出所有未被标记的点中编号最小的那个。

反例： $n=5$ ，只有 $5$ 可收买，边只有 $2\to1$ 。此时源分量是 $\{2\}$ （不可买）和 $\{5\}$ （可买）。从 $5$ 出发只能到 $5$ ，不可达集合是 $\{1,2,3,4\}$ ，正确答案是 $1$ ，而不是源分量里的 $2$ 。

代码

用 rbook 的 Tarjan 模板（book/code/graph/scc.cpp）求强连通分量：模板提供 scc.set(n)、scc.solve()，结果在 scc.scc_id[v]（从 $1$ 开始）与 scc.scc_cnt。模板依赖链式前向星 e.h[u] / e[i].next，所以下面把 linkList 一并带上，使文件能独立编译。

接着一次遍历统计每个分量的最小价、一次遍历统计跨分量入度（环内的边不能计入，否则环上每个分量的入度都会被自己凑成非 $0$ ），再一轮 BFS 判可达。

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/**
 * 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-22 18:20
 * update_at: 2026-10-22 18:20
 */
// P1262 [POI 1996 R3] 间谍网络
//
// 建模：间谍是点，A 掌握 B 的证据是从 A 到 B 的有向边，「控制」就是沿边可达。
// 一旦买下某人，他的整条下游都免费到手，所以真正要决策的只是「从哪些点进入」。
// 互相可达的一批人（强连通分量）里买最便宜的即可，缩点后得到 DAG；
// DAG 中每个点都能上溯到某个入度为 0 的分量，那些分量无人能揭发、只能直接收买。
// 于是答案 = 每个入度为 0 的分量内最便宜的可收买价之和。
//
// 强连通分量用 rbook 的 Tarjan 模板（book/code/graph/scc.cpp）。
// n <= 3000，递归深度最多 3000，栈空间安全，按模板直接递归。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3005;
const int maxe = 8005;
const int INF = 1e9;  // 贿赂价上限 20000，INF 不会与任何真实价格相撞

// 链式前向星，与 linklist.cpp 同结构：Tarjan 模板里的 e.h / e[i].next 都由它提供。
struct linkList {
    typedef struct { int u, v, w, next; } edge;
    edge e[maxe];
    int h[maxn], edge_cnt = 0;
    linkList() { reset(); }

    void reset() {
        edge_cnt = 0;
        memset(h, -1, sizeof(h));
    }
    void add(int u, int v, int w = 0) {
        e[edge_cnt] = {u, v, w, h[u]};
        h[u] = edge_cnt++;
    }
    edge& operator[](int i) { return e[i]; }
} e;

struct TarjanScc {
    int n, timer;
    std::stack<int> st;
    bool in_stack[maxn];
    int dfn[maxn], low[maxn], scc_id[maxn];
    int scc_cnt;  // SCC 的总数

    void set(int _n) {
        n = _n;
        timer = scc_cnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(in_stack, 0, sizeof(in_stack));
    }

    // 有向图,不要加father参数
    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

        for (int i = e.h[u]; ~i ; i = e[i].next) {
            int v = e[i].v;
            if (!dfn[v]) {  // 如果 v 没被访问过
                dfs(v);

                // 根据子节点的 low 值更新当前节点的 low 值
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) {  // 返祖边, 如果 v 在栈中，说明构成了环
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        // 如果 dfn == low，说明找到了一个 SCC 的起始点
        if (low[u] == dfn[u]) {
            scc_cnt++;
            while (1) {
                int v = st.top(); st.pop();
                in_stack[v] = 0;
                scc_id[v] = scc_cnt;  // 标记所属 SCC 编号
                if (v == u) break;    // 直到找到起始点
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) dfs(i);
        }
    }
} scc;

int n, p, r;

int cost[maxn];      // cost[v] = 收买 v 的价格，INF 表示不可收买
int min_cost[maxn];  // min_cost[c] = 分量 c 内最便宜的可收买价
int indeg[maxn];     // 缩点后分量 c 的入度，只统计跨分量的边
bool reach[maxn];    // 从所有可收买点出发能否到达

void read_input() {
    cin >> n;
    cin >> p;
    fill(cost, cost + n + 1, INF);
    for (int i = 0; i < p; i++) {
        int v, c;
        cin >> v >> c;
        cost[v] = c;
    }
    cin >> r;
    for (int i = 0; i < r; i++) {
        int u, v;
        cin >> u >> v;
        e.add(u, v);
    }
}

void solve() {
    scc.set(n);
    scc.solve();
    int cnt = scc.scc_cnt;

    fill(min_cost, min_cost + cnt + 1, INF);
    for (int v = 1; v <= n; v++) {
        int c = scc.scc_id[v];
        min_cost[c] = min(min_cost[c], cost[v]);
    }

    // 缩点后 DAG 的入度：环内的边不算，否则环上的分量入度都被自己凑成非 0
    for (int u = 1; u <= n; u++) {
        for (int i = e.h[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if (scc.scc_id[u] != scc.scc_id[v]) indeg[scc.scc_id[v]]++;
        }
    }

    // 买下所有可收买者能控制的范围：买得越多只会更广，所以全买就是最大可达集。
    // 谁都不在其中，就永远无法控制。
    {
        std::queue<int> q;
        for (int v = 1; v <= n; v++) {
            if (cost[v] < INF) {
                reach[v] = true;
                q.push(v);
            }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = e.h[u]; ~i; i = e[i].next) {
                int v = e[i].v;
                if (!reach[v]) {
                    reach[v] = true;
                    q.push(v);
                }
            }
        }
    }

    // 注意：这里要找「所有不可达点里编号最小的」，不是「坏分量里编号最小的」。
    // 坏分量的下游同样失控，而那些点的编号可能更小。
    int bad = 0;
    for (int v = 1; v <= n; v++) {
        if (!reach[v]) { bad = v; break; }
    }
    if (bad) {
        cout << "NO\n" << bad << "\n";
        return;
    }

    long long total = 0;  // 最坏 3000 * 20000 = 6e7，int 够，统一用 long long
    for (int c = 1; c <= cnt; c++) {
        if (indeg[c] == 0) total += min_cost[c];
    }
    cout << "YES\n" << total << "\n";
}

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

    read_input();
    solve();

    return 0;
}

同一套算法在 Python 下的写法与 C++ 对应，但有两点必须换：分量用迭代 Tarjan，读入用一次 split() 顺序消费。

Python 必须改成迭代的原因不是风格偏好，而是 $n$ 最大 $3000$ 超过默认递归上限 $1000$ ，直接递归会 RuntimeError。rbook 的 book/code/graph/scc.py 本身就是用"栈帧记录下一条待处理出边"的迭代版，下面沿用它，并且不靠 setrecursionlimit 掩盖问题。

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
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"""P1262 [POI 1996 R3] 间谍网络

建模：间谍是点，A 掌握 B 的证据是从 A 到 B 的有向边，「控制」就是沿边可达。
买下某人后他的整条下游免费到手，所以真正要决策的只是「从哪些点进入」。
互相可达的一批人（强连通分量）里买最便宜的即可，缩点后得到 DAG；
DAG 中每个点都能上溯到某个入度为 0 的分量，那些分量无人能揭发、只能直接收买，
所以答案 = 每个入度为 0 的分量内最便宜的可收买价之和。

强连通分量用 rbook 的 Tarjan 模板（book/code/graph/scc.py）。
模板的 dfs 是显式栈写法：n 最大 3000，超过 Python 默认递归上限 1000，
直接递归会 RuntimeError，这里沿用模板的迭代实现，不加 setrecursionlimit。
"""

import sys
from collections import deque

INF = 10 ** 9  # 贿赂价上限 20000，INF 不会与任何真实价格相撞


class LinkList:
    """链式前向星，与 linklist.py 同结构：Tarjan 模板的 e.h / e[i].next 都由它提供。"""

    def __init__(self) -> None:
        self.edge_cnt = 0
        self.ev: list[int] = []  # 第 i 条边的终点
        self.enext: list[int] = []  # 第 i 条边的下一条出边编号
        self.h: list[int] = []  # h[u] = u 的第一条出边编号，-1 表示没有

    def reset(self, n: int) -> None:
        self.edge_cnt = 0
        self.ev = []
        self.enext = []
        self.h = [-1] * (n + 1)

    def add(self, u: int, v: int) -> None:
        self.ev.append(v)
        self.enext.append(self.h[u])
        self.h[u] = self.edge_cnt
        self.edge_cnt += 1


def tarjan(n: int, graph: LinkList) -> tuple[list[int], int]:
    """求强连通分量，返回 (scc_id, scc_cnt)；scc_id 从 1 开始。

    与 book/code/graph/scc.py 的迭代实现一致：栈帧记录 (节点, 下一条待处理的出边编号)，
    回溯时把子节点的 low 并回父节点，dfn == low 时弹出整个分量。
    """
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    scc_id = [0] * (n + 1)
    in_stack = [False] * (n + 1)
    st: list[int] = []
    scc_cnt = 0
    timer = 0

    for start in range(1, n + 1):
        if dfn[start]:
            continue
        timer += 1
        dfn[start] = low[start] = timer
        st.append(start)
        in_stack[start] = True
        call: list[tuple[int, int]] = [(start, graph.h[start])]

        while call:
            u, i = call[-1]
            advanced = False
            while i != -1:
                v = graph.ev[i]
                i = graph.enext[i]
                if dfn[v] == 0:
                    call[-1] = (u, i)
                    timer += 1
                    dfn[v] = low[v] = timer
                    st.append(v)
                    in_stack[v] = True
                    call.append((v, graph.h[v]))
                    advanced = True
                    break
                if in_stack[v]:
                    # 返祖边：只能回到栈中的点，用 dfn[v] 更新 low[u]
                    low[u] = min(low[u], dfn[v])
            if advanced:
                continue

            call.pop()
            if low[u] == dfn[u]:
                scc_cnt += 1
                while True:
                    v = st.pop()
                    in_stack[v] = False
                    scc_id[v] = scc_cnt
                    if v == u:
                        break
            if call:
                # 递归返回后 low[父] = min(low[父], low[子])
                pu = call[-1][0]
                low[pu] = min(low[pu], low[u])

    return scc_id, scc_cnt


def solve(n: int, cost: list[int], graph: LinkList) -> tuple[str, int]:
    scc_id, scc_cnt = tarjan(n, graph)

    # 分量内最便宜的可收买价
    min_cost = [INF] * (scc_cnt + 1)
    for v in range(1, n + 1):
        c = scc_id[v]
        min_cost[c] = min(min_cost[c], cost[v])

    # 缩点后 DAG 的入度：环内的边不算，否则环上分量的入度都被自己凑成非 0
    indeg = [0] * (scc_cnt + 1)
    for u in range(1, n + 1):
        i = graph.h[u]
        while i != -1:
            v = graph.ev[i]
            if scc_id[u] != scc_id[v]:
                indeg[scc_id[v]] += 1
            i = graph.enext[i]

    # 买下所有可收买者能控制的范围：买得越多只会更广，全买就是最大可达集
    reach = [False] * (n + 1)
    q: deque[int] = deque()
    for v in range(1, n + 1):
        if cost[v] < INF:
            reach[v] = True
            q.append(v)
    while q:
        u = q.popleft()
        i = graph.h[u]
        while i != -1:
            v = graph.ev[i]
            if not reach[v]:
                reach[v] = True
                q.append(v)
            i = graph.enext[i]

    # 注意：要找「所有不可达点里编号最小的」，不是「坏分量里编号最小的」，
    # 因为坏分量的下游同样失控，而那些点的编号可能更小。
    for v in range(1, n + 1):
        if not reach[v]:
            return ("NO", v)

    total = 0
    for c in range(1, scc_cnt + 1):
        if indeg[c] == 0:
            total += min_cost[c]
    return ("YES", total)


def main() -> None:
    data = sys.stdin.buffer.read().split()
    pos = 0
    n = int(data[pos]); pos += 1
    p = int(data[pos]); pos += 1

    cost = [INF] * (n + 1)
    for _ in range(p):
        v = int(data[pos]); pos += 1
        c = int(data[pos]); pos += 1
        cost[v] = c

    graph = LinkList()
    graph.reset(n)
    r = int(data[pos]); pos += 1
    for _ in range(r):
        u = int(data[pos]); pos += 1
        v = int(data[pos]); pos += 1
        graph.add(u, v)

    verdict, value = solve(n, cost, graph)
    sys.stdout.write(f"{verdict}\n{value}\n")


if __name__ == "__main__":
    main()

复杂度

$n \leqslant 3000$ 、 $r \leqslant 8000$ ，两者都是线性级别：

Tarjan 求分量： $O(n+r)$ ；
统计分量最小价与跨分量入度： $O(n+r)$ ；
可达性 BFS： $O(n+r)$ 。

总时间 $O(n+r)$ ，空间 $O(n+r)$ 。

答案上界是 $3000 \times 20000 = 6\times 10^7$ ，int 也不会溢出，代码里仍统一用 long long 兜底。

实测（roj-local-judge-lite， $n=3000$ 满规模）：C++ 约 $3$ ms、内存不足 $1$ MB；Python 约 $30$ ms。把栈限制压到 $1$ MiB 跑 $3000$ 深的长链仍然 AC，说明 C++ 的递归写法安全。

总结

这题的关键动作是把"选择哪些人"换成"从哪些人进入"。

一旦接受"控制是单向传递、下游免费到手"，可收买者的子集枚举就变成了入口选择；而"互相可达"这个等价关系又把入口归并成强连通分量，缩点后的 DAG 里只剩入度为 $0$ 的分量是非买不可的。必要性和充分性各用一句话就能说清，问题从 $O(2^p)$ 降到 $O(n+r)$ 。

值得带走的两个细节：

缩点后统计入度时必须跳过环内边，否则环上分量的入度会被自己填成非零，这些分量就被误判成"不必买"；
无解时输出的是所有不可达点里编号最小的，不是坏分量的最小编号——坏分量的下游同样失控，而那些点编号可能更小。

把本题映射到离散数学：强连通是等价关系，缩点就是取商集，缩点图是 DAG（偏序）；入度为 $0$ 的分量是这个偏序的极小元，而"买下所有极小元即可覆盖全序"正是"有限偏序中每个元素都被某个极小元支配"这一基本性质。