费用流线性规划对偶的构造方案

· · 算法·理论

十分感谢 142857cs 和 ppip 的帮助！

本文的记号和费用流对偶标准形式与丁晓漫集训队论文 4.1.1 部分相同。

先给出算法：在费用流的残量网络上，每条边的边的边权为它的费用，然后建立超级源点向每个点连边权为 0 的边，跑最短路即可。正确性证明：

记 u,v 边的流量为 f_{u,v}，这里不考虑反边的流量为正边的相反数，所以有 0\le f_{u,v}\le c_{u,v}。

我们要证明的是用这种方法构造出来的 p 计算出的答案等于费用流算出的答案，即：

\sum_ub_up_u+\sum c_{u,v}\max(0,p_v-p_u-w_{u,v})=-\sum f_{u,v}w_{u,v}

若 f_{u,v}<c_{u,v}，则这条边在残量网络上，根据最短路的性质可以推出 p_v-p_u-w_{u,v}\le0，即 \max(0,p_v-p_u-w_{u,v})=0。所以

\sum c_{u,v}\max(0,p_v-p_u-w_{u,v})=\sum f_{u,v}\max(0,p_v-p_u-w_{u,v})

若 f_{u,v}>0，则这条边的反边在残量网络上，根据最短路的性质可以推出 p_v-p_u-w_{u,v}\ge0，即 \max(0,p_v-p_u-w_{u,v})=p_v-p_u-w_{u,v}。所以

\sum f_{u,v}\max(0,p_v-p_u-w_{u,v})=\sum f_{u,v}(p_v-p_u-w_{u,v})

根据流量平衡

\forall u,\sum_vf_{v,u}-\sum_vf_{u,v}=-b_u

有

\sum f_{u,v}(p_v-p_u-w_{u,v})=-\sum_ub_up_u-\sum f_{u,v}w_{u,v}

得证。