ABC326G 题解

发布时间 2023-11-05 11:44:02作者: liangbowen

blog。简单最小割。


发现 \(L_{i,j}\le5\),所以对 Level 拆点。初始源点 \(S\xrightarrow{0} \text{Lvl}1_i, S\xrightarrow{c_i} \text{Lvl}2_i,\text{Lvl}3_i,\text{Lvl}4_i,\text{Lvl}5_i\),表示当前是 \(\text{level }1\),每升一级就要多买个 \(c_i\)

每个成就向汇点连 \(a_i\) 的边,割掉这条边,表示你可以不满足这个成就,但是你会少获得 \(a_i\) 元。

code,时间复杂度 \(O(\text{能过})\)