保序回归 p=1 问题的费用流解法
b6e0_
·
·
算法·理论
保序回归 p=1 问题的标准形式为，给定一张有向图，每个点有 w_i,y_i(w_i>0)，你需要求一组 x_i，满足：
- 对于图中每条 u\to v 的边，x_u\le x_v；
-
一种做法是整体二分，见高睿泉《浅谈保序回归问题》，2018 年集训队论文。
考虑费用流线性规划对偶的标准形式：
\min\sum b_ix_i+\sum_{u,v}c_{u,v}\max(0,x_v-x_u-w_{u,v})
在保序回归里，x_u\le x_v 的限制可以看做 (+\infty)\cdot\max(0,x_u-x_v)；|x_i-y_i| 可以看做是 |x_i-x_0-y_i|（其中 x_0 是任何数都可以，无非是把 x_i 全部加上一个数），然后拆成 \max(0,x_i-x_0-y_i)+\max(0,x_0-x_i-(-y_i))。所以我们可以利用对偶建出费用流。对图做一些简化后，算法流程为：
- 源点向 i 连 (2w_i,y_i) 的边；
-
- 对于原图中 u\to v 的边，网络中 v 向 u 连 (+\infty,0) 的边；
- 跑最小费用最大流，记最小费用为 C，\sum w_iy_i-C 即为原问题答案。
于是这题的贪心做法也可以看做是模拟费用流。
关于构造方案，见我的这篇文章。