T30913: 猫猫逛公园
SCC, http://cs101.openjudge.cn/practice/30913/
黄色的树林里分出两条路， 可惜我不能同时去涉足， 我在那路口久久伫立， 向着一条路极目望去， 直到它消失在丛林深处。
猫猫要去公园散步。
公园里有 n 个岔路口，通过 m 条有向路径相互连接。在每条路径上都有一些美丽的风景。猫猫给每条路径上的风景都打了分，第 i 条路径上的风景值为 wi，猫猫经过一次就可以获得 wi 的愉悦度。但是，猫猫对重复的风景也会厌倦，具体地，如果猫猫已经经过了 k 次某条路径，那么在第 k+1 次经过时，风景值会比上一次经过时减少 k。如果风景值被减少到 <= 0，猫猫将不再获得愉悦度。为了方便计算，猫猫帮你推导好了以下公式：
例如，若某路径上最初的风景值为 9，那么猫猫从第一次到第四次途经时依次能获得 9, 8, 6, 3 的愉悦度。从第五次及以后，猫猫将无法再从这条路径上获得任何愉悦度，但仍然可以经过该路径，也不会获得负的愉悦度。
因为路径是有向的，所以猫猫可能不能完全游览所有的路径直到所有路径的风景值 <= 0，甚至不能游览每一条路径各一次！那些未选择的路，只能成为遗憾了。
猫猫决定从第 s 个岔路口开始出发游览公园。请问猫猫最多能在公园里面获得多少愉悦度？
输入
第一行包含两个整数 n 和 m（1 <= n <= 10^5，0 <= m <= 2 * 10^5），分别表示公园里的岔路口数量和有向路径数量。 接下来的 m 行，每行包含三个整数 xi、yi 和 wi（1 <= xi, yi <= n，0 <= wi <= 10^8），表示一条从岔路口 xi 到岔路口 yi 的有向路径，路径上最初的风景值为 wi。允许从某个岔路口到自身的路径，也允许两个岔路口之间存在多条路径。
最后一行包含一个整数 s（1 <= s <= n），表示猫猫的起始位置。
输出
输出一个整数，表示猫猫在游览中最多能够获得的愉悦度。
样例输入
sample1 input:
2 2
1 2 4
2 1 4
1
sample2 input:
3 3
1 2 4
2 3 3
1 3 8
1
sample3 input:
10 11
1 10 8
10 9 8
9 1 8
1 7 16777216
8 7 1048576
3 8 20
3 6 7
6 5 10
5 2 10
2 6 10
6 8 3
3样例输出
sample1 output:
16
sample2 output:
8
sample3 output:
1048676提示
SCC, Topological Order, DP（强连通，拓扑排序，动态规划） 样例 3 是猫猫手动构造的强数据，特意加上方便调试的。 共 100 个测试点，总输入不超过 100MB
来源：2026 spring, RainFestival
import sys
def solve():
# 使用 sys.stdin.read 快速读取输入，防止 I/O 成为瓶颈
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
m = int(input_data[1])
adj = [[] for _ in range(n + 1)]
radj = [[] for _ in range(n + 1)]
idx = 2
for _ in range(m):
u = int(input_data[idx])
v = int(input_data[idx + 1])
w = int(input_data[idx + 2])
adj[u].append((v, w))
radj[v].append(u)
idx += 3
s = int(input_data[idx])
# ---------------- Kosaraju 算法求强连通分量 (SCC) ----------------
# 步骤 1：在原图上运行非递归 DFS，求得后序遍历序列
visited = [False] * (n + 1)
order = []
for i in range(1, n + 1):
if not visited[i]:
state_stack = [(i, 0)]
visited[i] = True
while state_stack:
u, edge_idx = state_stack[-1]
if edge_idx < len(adj[u]):
v, _ = adj[u][edge_idx]
state_stack[-1] = (u, edge_idx + 1)
if not visited[v]:
visited[v] = True
state_stack.append((v, 0))
else:
order.append(u)
state_stack.pop()
# 步骤 2：在反图上，按照后序遍历的逆序进行非递归 DFS，划分 SCC
visited2 = [False] * (n + 1)
scc_id = [-1] * (n + 1)
scc_count = 0
for u in reversed(order):
if not visited2[u]:
stack = [u]
visited2[u] = True
while stack:
curr = stack.pop()
scc_id[curr] = scc_count
for v in radj[curr]:
if not visited2[v]:
visited2[v] = True
stack.append(v)
scc_count += 1
# ---------------- 榨干单条边能获得的最大愉悦度 ----------------
def harvest(w):
if w <= 0:
return 0
# 求解 T * (T - 1) / 2 < w 时的最大正整数 T
val = 1 + 8 * w
r = int(val**0.5)
T = (1 + r) // 2
# 对 T 进行微调以确保 100% 精确
while T * (T - 1) // 2 >= w:
T -= 1
while (T + 1) * T // 2 < w:
T += 1
return T * w - (T - 1) * T * (T + 1) // 6
# ---------------- 缩点构建 DAG ----------------
scc_val = [0] * scc_count
dag_edges = [{} for _ in range(scc_count)]
for u in range(1, n + 1):
su = scc_id[u]
for v, w in adj[u]:
sv = scc_id[v]
if su == sv:
# 强连通分量内部的边可以被无限次榨干
scc_val[su] += harvest(w)
else:
# 强连通分量之间的跨越边，只能走一次，多条边时保留权值最大的一条
if sv not in dag_edges[su] or dag_edges[su][sv] < w:
dag_edges[su][sv] = w
# ---------------- 拓扑排序 (Kahn 算法) ----------------
in_degree = [0] * scc_count
for su in range(scc_count):
for sv in dag_edges[su]:
in_degree[sv] += 1
from collections import deque
queue = deque([i for i in range(scc_count) if in_degree[i] == 0])
topo_order = []
while queue:
u = queue.popleft()
topo_order.append(u)
for v in dag_edges[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
# ---------------- DAG 上的动态规划 (DP) ----------------
dp = [-1] * scc_count
scc_s = scc_id[s]
dp[scc_s] = scc_val[scc_s]
for u in topo_order:
if dp[u] == -1:
continue
for v, w in dag_edges[u].items():
val = dp[u] + w + scc_val[v]
if val > dp[v]:
dp[v] = val
# 最大的愉悦度是所有可达节点中 dp 值的最大值
print(max(dp))
if __name__ == "__main__":
solve()