QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2025-12-14 07:11:42

Last updated: 2025-12-14 07:11:47

Back to Problem

题解

无环等价于每个点至多被两个区间覆盖,求最大的权值和。这是一个经典问题,可以用最小费用流解决:

  • 对每个区间,从 $s_i-1$ 到 $e_i$ 连边容量 $1$,费用 $-w_i$。
  • 对每个 $x\pod{0\le x<\max\{e_i\}}$,从 $x$ 到 $x+1$ 连边容量 $+\infty$,费用 $0$。

从 $0$ 到 $\max\{e_i\}$ 的流量为 $2$ 的最小费用流的相反数即为答案。注意初始时图中有负边,但是是 DAG,在使用 Dijkstra 算法时将点 $u$ 的势能设为 $-10^{12}\cdot u$ 即可。

时间复杂度 $O(N\log N)$。

Comments

No comments yet.