NOI2018模拟赛(四十二)

有 \(n\) 个数,求一个排列,使其最大字段和最大。有 \(m\) 个条件形如 \(x_i\) 必须在 \(x_j\) 之前。

网络流,拆点 \(x_{i1},x_{i2}\),连边 \(S\rightarrow x_{i1}\rightarrow x_{i2}\rightarrow T\)。

割三条边分别表示与最大子段的位置关系。限制条件连边 \(x_{i1}\rightarrow x_{j1},x_{i2}\rightarrow x_{j2}\),容量 \(\infty\)。


在《NOI2018模拟赛(四十二)》上留下第一个评论