Tarjan 缩点把环内收益合并为分量点权和，再在缩点 DAG 上按分量编号降序做最长路 DP，线性时间求出起点到任意酒吧的最大收益。
OJ: roj
题目 ID: 1518
难度:提高+/省选-
标签:强连通分量Tarjan缩点拓扑排序动态规划图论python
创建: 2026-09-30 15:55
更新: 2026-10-07 12:15
前置题目
HDU 3836Equivalent SetsA 教的 Tarjan 求 SCC 后缩点成 DAG 这一步被 B 完整复用（main.py 的 tarjan_scc 与 comp 缩点，正解亦以此为等价变换），B 只是在缩点 DAG 上叠加分量权值合并与最长路 DP，属典型模板级台阶。HDU 3072Intelligence SystemB 的 pool[c] 合并正是复用 A 教的「SCC 内部互相可达、整体合并成一点」这一关键观察，只是把 A 的内部费用忽略改成内部收益求和，再叠加缩点 DAG 上的最长路 DP。luogu P3275[SCOI2011] 糖果B 沿用了 A 的“SCC 缩点成 DAG 后求最长路”这一步：A 用分量初值 1 求最小糖果，B 换成以分量点权和 pool 为初值、按分量编号降序做最长路 DP
形式化题目
给定一张
Banditji 从
其中
样例
题面样例的图如下（节点编号写在圆圈内，权值写在节点下方）：
flowchart LR
n1(("1<br/>10")) --> n2(("2<br/>12"))
n2 --> n3(("3<br/>8"))
n3 --> n5(("5<br/>1"))
n2 --> n4(("4<br/>16"))
n4 --> n1
n2 --> n6(("6<br/>5"))
n6 --> n5
这条路线把
正解
思路
朴素想法的困境
最直接的思路是枚举从
关键观察：强连通分量内部可以全部扫空
设
这一步消掉了唯一的自由度——"分量内部怎么走"不再是一个需要决策的问题。
缩点，把问题变成 DAG 最长路
把每个 SCC 收缩成一个新点，跨分量的边保留。缩点后的图一定是 DAG：
若仍有环
于是原问题严格等价于：在缩点 DAG 上，从
样例缩点后得到 4 个分量（括号内为权和）：
flowchart LR
C3["comp3<br/>{1,2,4}<br/>pool = 38"] --> C2["comp2<br/>{3}<br/>pool = 8"]
C2 --> C0["comp0<br/>{5}<br/>pool = 1"]
C3 --> C1["comp1<br/>{6}<br/>pool = 5"]
C1 --> C0
缩点前 6 个点、3 条跨分量边，缩点后只剩 4 个点。注意
DP 转移
在 DAG 上做最长路，转移为
初值
因为权值非负，我们已经把"能到的分量全都拿"内建进了
| 处理顺序 | 当前分量的 |
松弛后 |
|||
|---|---|---|---|---|---|
| 初始 | — | ||||
表中每行是"处理完编号为
一个实现上的便利：Tarjan 的编号自带拓扑序
不必真的把缩点图建出来再拓扑排序。Tarjan 是在子树全部处理完之后才弹出分量并 给它编号的，因此后继分量一定先拿到更小的编号：
所以让
其余实现要点
- 迭代 DFS：
可达 50 万，递归 Tarjan 会爆栈，用显式 work栈模拟； - 保护邻接表：Tarjan 需要"下一条待处理边"的游标，用
head的副本承载， DP 阶段还要用完整的head再扫一遍出边； - 分桶遍历分量成员：DP 要按分量编号顺序访问分量内的点，用计数排序分桶做到
； - 64 位：分量权和最大约
，超出 32 位， dp用array('q')。
代码
Python 版：
python
#!/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:55
# update_at: 2026-09-30 15:55
import sys
from array import array
NEG = -(1 << 60) # 不可达哨兵；金额非负，用它区分"还没走到过"
def tarjan_scc(n: int, head: array, nxt: array, to: array) -> tuple[array, int]:
"""迭代式 Tarjan 求强连通分量，返回 (comp, 分量个数)。
分量在"子树全部处理完"时才弹出并编号，所以后继分量一定先拿到小编号：
对跨分量的边 u -> v 恒有 comp[u] > comp[v]。也就是说 comp 的降序就是拓扑序，
DP 时从 ncomp-1 往 0 扫即可，无需再排序。
用人工栈模拟递归，避免 50 万点把 Python 递归深度打爆。
`cur` 是 head 的副本，函数会把它当"每个点下一条待处理边"的游标改掉，
调用方的 head 保持原样，后面缩点 DP 还要用完整的邻接表。
"""
cur = array('i', head) # 游标副本，避免破坏调用方的 head
dfn = array('i', [-1]) * n # 访问时间戳，-1 表示还没访问
low = array('i', [0]) * n # 子树经回边能触到的最小 dfn
comp = array('i', [-1]) * n
on = bytearray(n) # 是否还在 Tarjan 的 SCC 栈里
scc: list[int] = [] # 待判定的 SCC 栈
work: list[int] = [] # 人工递归栈：存待处理的节点
timer = 0
cnt = 0
for root in range(n):
if dfn[root] >= 0:
continue
dfn[root] = low[root] = timer
timer += 1
scc.append(root)
on[root] = 1
work.append(root)
while work:
v = work[-1]
e = cur[v] # 取 v 下一条还没处理的出边
if e == -1: # 出边处理完，可以收尾
work.pop()
if low[v] == dfn[v]: # v 是所在 SCC 的根，弹出整个分量
while True:
u = scc.pop()
on[u] = 0
comp[u] = cnt
if u == v:
break
cnt += 1
if work and low[v] < low[work[-1]]:
low[work[-1]] = low[v] # 子树 low 回传给父亲
continue
cur[v] = nxt[e] # 这条边走过了，下次从下一条继续
u = to[e]
if dfn[u] < 0: # 树边：新节点入栈
dfn[u] = low[u] = timer
timer += 1
scc.append(u)
on[u] = 1
work.append(u)
elif on[u] and dfn[u] < low[v]: # 回边/横叉边：只有仍在栈里的才更新 low
low[v] = dfn[u]
return comp, cnt
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
m = next(data)
# 链式前向星：head[v] 是 v 的第一条出边，nxt[e] 是同起点的下一条边。
# 用 array('i') 而非 list：50 万点 50 万边下 list 的指针开销会顶到内存上限。
head = array('i', [-1]) * n
nxt = array('i', [0]) * m
to = array('i', [0]) * m
for e in range(m):
a = next(data) - 1
b = next(data) - 1
to[e] = b
nxt[e] = head[a]
head[a] = e
money = array('i', [0]) * n # 题面的每台 ATM 金额，非负
for v in range(n):
money[v] = next(data)
start = next(data) - 1 # 市中心 S
bar_cnt = next(data) # 酒吧数目 P
bar = bytearray(n)
for _ in range(bar_cnt):
bar[next(data) - 1] = 1
comp, ncomp = tarjan_scc(n, head, nxt, to)
# 缩点：分量内任意两点互达，走到一个点就能把整个分量的钱扫空，故按分量求和。
pool = array('q', [0]) * ncomp
has_bar = bytearray(ncomp)
for v in range(n):
c = comp[v]
pool[c] += money[v]
if bar[v]:
has_bar[c] = 1
# 把节点按分量分桶（计数排序），这样能按分量编号顺序遍历"分量内的点"。
# comp 降序 = 拓扑序，一趟倒序扫描即可完成 DAG 上的最长路（松弛只向编号更小处走）。
bucket_start = array('i', [0]) * (ncomp + 1)
for v in range(n):
bucket_start[comp[v] + 1] += 1
for c in range(ncomp):
bucket_start[c + 1] += bucket_start[c]
fill = array('i', bucket_start[:ncomp]) # 每个桶当前的写入位置
node_of = array('i', [0]) * n
for v in range(n):
c = comp[v]
node_of[fill[c]] = v
fill[c] += 1
# dp[c] = 从 S 出发走到分量 c 时能抢到的最大金额（含 c 自己的钱）。
dp = array('q', [NEG]) * ncomp
dp[comp[start]] = pool[comp[start]]
best = NEG
for c in range(ncomp - 1, -1, -1): # 分量编号降序 = 缩点 DAG 的拓扑序
if dp[c] == NEG: # 这个分量从 S 根本走不到，跳过
continue
if has_bar[c] and dp[c] > best: # 任意酒吧都能收尾，随时刷新答案
best = dp[c]
for i in range(bucket_start[c], bucket_start[c + 1]):
e = head[node_of[i]]
while e != -1:
u = comp[to[e]]
if u != c and dp[c] + pool[u] > dp[u]: # 只沿跨分量的边松弛
dp[u] = dp[c] + pool[u]
e = nxt[e]
sys.stdout.write(str(best) + '\n')
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:58
* update_at: 2026-10-05 05:58
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int MAXM = 500005;
typedef long long ll;
const ll NEG = -(1LL << 60); // 不可达哨兵；金额非负，用它区分"没走到过"和"收益为 0"
int n, m;
// 链式前向星：head[v] 是 v 的第一条出边编号，0 表示没有出边。
int head[MAXN];
int to[MAXM];
int nxt[MAXM];
int edge_cnt;
int money[MAXN]; // 每个路口的 ATM 金额，非负且不超过 4000
char bar[MAXN]; // bar[v] = 1 表示路口 v 有酒吧
// Tarjan 需要的全局数组。
int cur[MAXN]; // 每个点下一条待处理出边的游标，是 head 的副本，避免破坏 head
int dfn[MAXN]; // 访问时间戳，0 表示还没访问
int low[MAXN]; // 子树经回边能触到的最小 dfn
int comp[MAXN]; // 每个点所属的强连通分量编号
char on_stack[MAXN]; // 是否还在 Tarjan 的 SCC 栈里
int scc_stack[MAXN]; // 待判定的 SCC 栈
int work_stack[MAXN];// 人工递归栈，模拟 Tarjan 的深搜过程
int comp_cnt; // 强连通分量个数
// 缩点后的结果。
ll pool[MAXN]; // pool[c] = 分量 c 内所有路口金额之和
char has_bar[MAXN]; // has_bar[c] = 1 表示分量 c 里有酒吧
ll dp[MAXN]; // dp[c] = 从起点走到分量 c 时能抢到的最大金额（含 c 自己的钱）
int node_of[MAXN]; // 按分量编号分桶后的节点序列
int bucket_start[MAXN]; // 分量 c 的节点在 node_of 中的区间 [bucket_start[c], bucket_start[c+1])
int pos[MAXN]; // 分桶写入时的临时游标
// 加一条 u -> v 的边。
void add_edge(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
// 迭代式 Tarjan 求强连通分量，结果写入 comp[]，分量个数写入 comp_cnt。
// 分量在"子树全部处理完"后才弹出并编号，所以跨分量的边 u -> v 恒有 comp[u] > comp[v]，
// 也就是 comp 的降序天然就是缩点 DAG 的拓扑序。用人工栈代替递归，避免 50 万点爆栈。
void tarjan_scc() {
for (int v = 1; v <= n; v++) {
cur[v] = head[v];
}
int timer = 0;
int scc_top = 0;
int work_top = 0;
for (int root = 1; root <= n; root++) {
if (dfn[root] != 0) continue;
timer++;
dfn[root] = low[root] = timer;
scc_stack[++scc_top] = root;
on_stack[root] = 1;
work_stack[++work_top] = root;
while (work_top > 0) {
int v = work_stack[work_top];
int e = cur[v];
if (e == 0) {
// v 的出边全部处理完，可以收尾。
work_top--;
if (low[v] == dfn[v]) {
// v 是所在分量的根，弹出整个分量并编号。
while (true) {
int u = scc_stack[scc_top--];
on_stack[u] = 0;
comp[u] = comp_cnt;
if (u == v) break;
}
comp_cnt++;
}
if (work_top > 0) {
int parent = work_stack[work_top];
if (low[v] < low[parent]) low[parent] = low[v]; // 子树 low 回传给父亲
}
continue;
}
cur[v] = nxt[e]; // 这条边走过了，下次从下一条继续
int u = to[e];
if (dfn[u] == 0) {
// 树边：新节点入栈。
timer++;
dfn[u] = low[u] = timer;
scc_stack[++scc_top] = u;
on_stack[u] = 1;
work_stack[++work_top] = u;
} else if (on_stack[u] && dfn[u] < low[v]) {
// 回边或横叉边：只有仍在栈里的点才能更新 low。
low[v] = dfn[u];
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add_edge(a, b);
}
for (int v = 1; v <= n; v++) {
cin >> money[v];
}
int start, bar_cnt;
cin >> start >> bar_cnt;
for (int i = 1; i <= bar_cnt; i++) {
int v;
cin >> v;
bar[v] = 1;
}
tarjan_scc();
// 缩点：分量内任意两点互达，走进一个点就能把整个分量的钱扫空，故按分量求和。
for (int v = 1; v <= n; v++) {
int c = comp[v];
pool[c] += money[v];
if (bar[v]) has_bar[c] = 1;
}
// 计数排序：把节点按分量编号分桶，才能按分量顺序访问分量内的点。
for (int v = 1; v <= n; v++) {
bucket_start[comp[v] + 1]++;
}
for (int c = 1; c <= comp_cnt; c++) {
bucket_start[c] += bucket_start[c - 1];
}
for (int c = 0; c < comp_cnt; c++) {
pos[c] = bucket_start[c];
}
for (int v = 1; v <= n; v++) {
int c = comp[v];
node_of[pos[c]] = v;
pos[c]++;
}
// 在缩点 DAG 上做最长路 DP：dp[c] = pool[c] + max(dp[u])，u 是 c 的入边来源分量。
for (int c = 0; c < comp_cnt; c++) {
dp[c] = NEG;
}
dp[comp[start]] = pool[comp[start]];
ll best = NEG;
for (int c = comp_cnt - 1; c >= 0; c--) { // 分量编号降序 = 缩点 DAG 的拓扑序
if (dp[c] == NEG) continue; // 这个分量从起点根本走不到
if (has_bar[c] && dp[c] > best) {
best = dp[c]; // 停在任意一个有酒吧的分量都能收尾，随时刷新答案
}
for (int i = bucket_start[c]; i < bucket_start[c + 1]; i++) {
int v = node_of[i];
for (int e = head[v]; e != 0; e = nxt[e]) {
int u = comp[to[e]];
if (u != c && dp[c] + pool[u] > dp[u]) {
dp[u] = dp[c] + pool[u]; // 只沿跨分量的边松弛
}
}
}
}
cout << best << '\n';
return 0;
}tarjan_scc() 用人工栈实现 Tarjan，cur 是 head 的副本，承载"每个点下一条未处理
出边"的游标，因此调用方的 head 不会被破坏。solve() 读入后依次做：缩点聚合
pool/has_bar、计数排序分桶、按 range(ncomp - 1, -1, -1) 的降序做 DP。
NEG = -(1 << 60) 是不可达哨兵，用来把"没走到过的分量"与"收益为 0"区分开。
复杂度
- 时间：Tarjan
；缩点聚合 ；分桶 ； DP 阶段每个点、每条出边各扫一次 。总计 线性。 - 空间：邻接表与各辅助数组均为
，以 array/bytearray存放。 本地实测最大规模数据（、 ）峰值内存约 16 MB， 远低于 128 MB 限制；单组耗时约 0.02 s，远低于 1000 ms 限制。
总结
题目允许重复走点却只计一次钱，说明收益由点集决定而非路径。于是沿两条线索推进：
其一，同一个强连通分量内的点必然可以全部走到，收益直接合并成
核心不变量：每个分量的收益等于其内部权值和，且一旦可达就必定全拿（因为权值非负）。