费用流的对偶建模

考虑最大费用循环流的标准线性规划建模：

Maximize: $\sum_{i \in E}{cost_i \cdot f_i}$

• 对每条弧$i$有 $0 \leq f_i \leq cap_i$ ，$cap_i$ 表示这条弧的容量，$f_i \geq 0$。
• 对于每个点$x$有流量平衡: $\sum_{u_i = x}{f_i} - \sum_{v_i=x}{f_i} = 0$

共有$|V|+|E|$个限制，对偶后，设前$|V|$个限制对应的变量为$a_i$，后$|E|$个限制对应的变量为$d_i$，则变为如下线性规划模型：

Minimize: $\sum_{i \in E}{cap_i \cdot d_i}$

• 对每条弧$i$有 $a_{v_i} - a_{u_i} + d_i \geq cost_i$。
• $a_x$无限制，$d_i \geq 0$。

所以，比如有很多变量然后给定一些差分后的不等式然后可以花费代价让一个不等式“放宽”，目标总代价最小的模型，都是最大费用流的对偶。

---

举个栗子： SRM 676 Hard Farmville

有N种植物，种植某种植物之前都要保证某些植物已经种好了，这种关系没有环，用一个邻接矩阵表示。 第i种植物从种下到成熟需要t_i的时间，也可以使用c_i的钱使得这个时间减少1(不能减成负数)。 现在有C元钱，求种植所有植物的最小时间，多种植物可以同时种植。

原问题有很多入度为0或出度为0的点，不妨加一个超级起点连向所有点，加一个所有点都连向的超级终点。

先二分答案，然后问题转化成种植时间不超过$\lambda$时的最小花费。

设$x_i$为第$i$号植物的开始种植时间，$y_i$为第$i$号植物种好的时间，所以有以下不等式。

• 对于每条边$u \rightarrow v$，有$x_v \geq y_u$。
• 对于起点和终点$S,T$，有$x_S + \lambda \geq y_T$
• $y_i \geq x_i$
• $y_i \geq x_i + t_i - d_i$，$d_i$为i这个植物减少时间的次数。
• 最小化$\sum{d_i \cdot c_i}$

减少时间就正好对应着”花费代价让一个不等式放宽”的说法，所以根据对偶把上述不等式还原成每条弧的流量和费用，就把这个问题转化为了最大费用循环流。有些方程无法放宽等价于放宽它的代价无穷大，还原回来也就相当于某条弧的流量无穷大而已。