P3387 【模版】缩点 - 洛谷
给定一个有向图，每个点都有一个权值，允许多次经过一条边或者一个点但权值只计算一次。求一条权值之和最大的路径。
很明显的拓扑排序最长路问题，考虑缩点后进行 DP 。一般的方法为
- 缩点后得到 DAG ，在新的 DAG 里进行拓扑排序。
- 在拓扑排序的过程中更新状态转移方程
dp[v] = Max(dp[v], dp[u] + w[v])。
在进行收网时更新权值，此时新权值与 \(scc\) 的编号对应。
if dfn[x] == low[x]: # 其余模版省略t = 0while True:t += w[cur - 1]scc_size.append(t) # 得到一个SCC后其权值就是t索引与scc对应scc += 1
具体代码为
import sys
from math import inf
from collections import deque
sys.setrecursionlimit(100010)
if 1:inp = lambda: sys.stdin.readline().strip()II = lambda: int(inp())MII = lambda: map(int, inp().split())LII = lambda: list(MII())Max = lambda x, y: x if x > y else yMin = lambda x, y: x if x < y else ydef main():n, m = MII()w = LII()g = [[] for _ in range(n + 1)]for _ in range(m):u, v = MII()g[u].append(v)dfn = [-1] * (n + 1)low = [-1] * (n + 1)st = []inst = [False] * (n + 1)scc = 0timer = 1scc_id = [-1] * (n + 1)scc_size = []def tarjan(x):nonlocal timer, sccdfn[x] = low[x] = timertimer += 1st.append(x)inst[x] = Truefor y in g[x]:if dfn[y] == -1:tarjan(y)low[x] = Min(low[x], low[y])elif inst[y]:low[x] = Min(low[x], dfn[y])if dfn[x] == low[x]:t = 0while True:cur = st.pop()inst[cur] = Falsescc_id[cur] = scct += w[cur - 1]if cur == x:breakscc_size.append(t) scc += 1for i in range(1, n + 1):if dfn[i] == -1:tarjan(i)dag = [[] for _ in range(scc)]din = [0] * sccfor u in range(1, n + 1):for v in g[u]:su = scc_id[u]sv = scc_id[v]if su != sv:dag[su].append(sv)din[sv] += 1dq = deque([i for i in range(scc) if din[i] == 0])dist = [-inf] * sccfor i in dq:dist[i] = scc_size[i]while dq:u = dq.popleft()for v in dag[u]:dist[v] = Max(dist[v], dist[u] + scc_size[v])din[v] -= 1if din[v] == 0:dq.append(v)print(max(dist))if __name__ == "__main__":main()
如果只是单纯的在拓扑序上进行操作的话，其实可以不必要新建 DAG 。因为 Tarjan 算法得到的 scc_id 的顺序就是一个天然的逆拓扑序。
上面代码的 while 循环可以替换为以下代码
dist = scc_size[:]
# 可以去掉 din 数组和队列
for u in range(scc - 1, -1, -1):for v in dag[u]:dist[v] = Max(dist[v], dist[u] + scc_size[v])