CF1307G Cow and Exercise 【线性规划转对偶+费用流】

CF1307G Cow and Exercise

记 $S$ 为源点，$T$ 为汇点，流量为 $F$ ，费用为 $cost$ ，$f_{uv}$ 表示 $u$ 到 $v$ 的实际流量，$c_{uv}$ 表示 $u$ 到 $v$ 的流量限制，$w_{uv}$ 表示 $u$ 到 $v$ 的边权。

那么最小费用的线性规划形式则为
m i n { ∑ f u v w u v } { f u v ≤ c u v / / 流 量 限 制 ∑ v f v u ? ∑ v f u v = 0 ( u ≠ S , T ) / / 流 量 平 衡 ∑ v f v S ? ∑ v f S v = ? F ∑ v f v T ? ∑ v f T v = F f u v ≥ 0 min\{\sum f_{uv}w_{uv} \} \\ \begin{cases} f_{uv}\le c_{uv} &//流量限制 \\ \sum_v f_{vu}-\sum_v f_{uv}=0\ \ (u\ne S,T)\ \ &//流量平衡 \\ \sum_v f_{vS}-\sum_v f_{Sv}=-F \\ \sum_v f_{vT}-\sum_v f_{Tv}=F \\ f_{uv}\ge 0 \end{cases} min{ ∑fuv?wuv?}????????????????fuv?≤cuv?∑v?fvu??∑v?fuv?=0  (u??=S,T)  ∑v?fvS??∑v?fSv?=?F∑v?fvT??∑v?fTv?=Ffuv?≥0?//流量限制//流量平衡
转对偶问题，得到一个有 $n^2+n$ 个变量的线性规划。记前 $n^2$ 个喂 $x_{uv}$ ，后 $n$ 个为 $di{s}_i$ 。则对偶问题为：
m a x { F ? ( d i s T ? d i s S ) + ∑ x u v c u v } { x u v + d i s v ? d i s u ≤ w u v x u v ≤ 0 ， d i s i 无 限 制 max\{ F\cdot(dis_T-dis_S)+\sum x_{uv}c_{uv} \} \\ \begin{cases} x_{uv}+dis_v-dis_u\le w_{uv} \\ x_{uv}\le 0，dis_i无限制 \end{cases} max{ F?(disT??disS?)+∑xuv?cuv?}{ xuv?+disv??disu?≤wuv?xuv?≤0，disi?无限制?
将 $x_{uv}$ 取相反数可得：
m a x { F ? ( d i s T ? d i s S ) ? ∑ x u v c u v } { d i s v ≤ d i s u + w u v + x u v x u v ≥ 0 ， d i s i 无 限 制 max\{ F\cdot(dis_T-dis_S)-\sum x_{uv}c_{uv} \} \\ \begin{cases} dis_v\le dis_u+w_{uv}+x_{uv} \\ x_{uv}\ge 0，dis_i无限制 \end{cases} max{ F?(disT??disS?)?∑xuv?cuv?}{ disv?≤disu?+wuv?+xuv?xuv?≥0，disi?无限制?
观察约束条件可以发现，当 $di{s}_i$ 表示最短路，$x_{uv}$ 表示一条边增加的边权时，约束条件成立。那么 $\sum x_{uv}{c}_{uv}$ 就表示 $X$ （增加的边权和）。发现 $X$ 就是题目的 $x$ ，这就是题目的线性规划形式。（如果不严谨请轻喷233

联系原线性规划形式我们可以得到：（ $cost$ 为费用）
$$\begin{array}{rl}F?(di{s}_T?di{s}_S)?X& \le \sum f_{uv}{w}_{uv}\\ F?(di{s}_T?di{s}_S)?X& \le cost\\ di{s}_T?di{s}_S& \le \frac{cost+X}{F}\end{array}$$
所以我们现在要做的就是求最小的 $\frac{cost+X}{F}$ 。固定总流量是 $F$ ，跑费用流求最小的 $cost$ 。显然 $(F,cost)$ 是凸的，那么最小的 $\frac{cost+X}{F}$ 就可以三分来求。 $O(n^{2}m+q\log n)$ 。

我猜可能需要的前置知识_byYXY