P3337 [ZJOI2013]防守战线 题解

· · 题解

本文内容基本摘自 dxm 论文并对其作了部分注释。

费用流求解线性规划

考虑一个费用流。每条边 uv 的流量设为 f_{uv}，容量设为 c_{uv}，费用设为 w_{uv}。b_u 设为流出-流入。

限制形如 -f\ge -c，\sum_{v}f_{uv}-\sum_{v}f_{vu}=-b_u。目标形如 {\rm minimize} \sum fw。

取 -f_{uv} 的对偶变量 z_{uv}，p_u 为 \sum_{v}f_{uv}-\sum_{v}f_{vu} 的对偶变量。

限制形如 p_v-p_u-z_{uv} \le w_{uv}，目标形如 {\rm maximize} \sum-b_up_u-\sum cz。

含义是取了 p_v 个 \sum_{w}f_{vw}-\sum_{w}f_{wv}，取了 -p_u 个 \sum_{u}f_{uw}-\sum_{u}f_{wu}，取了 z_{uv} 个 -f_{uv}。 对于 {uv} 这条边来讲，这些系数加起来是要 \le w_{uv} 的。 （只有 f_{wv} 和 f_{uv} 有贡献。）

然后整理：

于是这就给我们提供了一个机械化的费用流求解形如上面问题的做法。 ### [ZJOI2013] 防守战线 若干限制形如 $\sum_{j=l_i}^{r_i} A_j \ge d_i$。${\rm minimize} \sum_{i=1}^nC_iA_i$。 sol：一种做法是直接对偶跑单纯型。 另一种做法是直接硬来。考虑设一个前缀和数组 $p$。那么限制就是 $p_{i+1}-p_i\ge 0, p_R-p_{L-1}\ge d_i$。 然后把后边那个用无限大的系数乘上就好了。目标函数就是 $$ \sum_{v}(C_v-C_{v+1})p_v+\sum_{v} \infty \max(0,p_i-p_{i+1})+\sum_{v} \infty \max(0,p_{L-1}-p_{R}+d_i) $$ 很好，就是上边的形式。然后写网络流。以下设 $(c,w)$ 表示容量为 $c$, 费用为 $w$。 是个多源多汇的形式。我们不妨令$C_v-C_{v+1}$为正的是源点，其余为汇点。从 $i+1$ 向 $i$ 连边 $(\infty,0)$，从 $R$ 向 $L-1$ 连边 $(\infty,-D_i)$，从 $n + 2$ 向源点加 $(C_v-C_{v+1},0)$，从汇点向 $n+1$ 连 $(C_{v+1}-C_{v},0)$。跑最小费用最大流后把答案取负数即可。 至于这个费用流的含义我没有细想过，感觉十分复杂。如果有简明的阐释麻烦教教，谢谢了。