CF1307G Cow and Exercise 【线性规划转对偶+费用流】-白红宇的个人博客

发布日期：2021-05-06 15:54:50 浏览次数：17 分类：技术文章

本文共 2233 字，大约阅读时间需要 7 分钟。

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

那么最小费用的线性规划形式则为

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}

转对偶问题，得到一个有

n^2+n

个变量的线性规划。记前

n^2

个喂

x_{uv}

，后

n

个为

dis_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}

将

x_{uv}

取相反数可得：

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}

观察约束条件可以发现，当

dis_i

表示最短路，

x_{uv}

表示一条边增加的边权时，约束条件成立。那么

\sum x_{uv}c_{uv}

就表示

X

（增加的边权和）。发现

X

就是题目的

x

，这就是题目的线性规划形式。（如果不严谨请轻喷233

联系原线性规划形式我们可以得到：（ $c o s t$ 为费用）

\begin{aligned} F\cdot(dis_T-dis_S)-X&\le\sum f_{uv}w_{uv} \\ F\cdot(dis_T-dis_S)-X&\le cost \\ dis_T-dis_S&\le \frac{cost+X}{F} \\ \end{aligned}

所以我们现在要做的就是求最小的

\frac{cost+X}{F}

。固定总流量是

F

，跑费用流求最小的

c o s t

。显然

(F, c o s t)

是凸的，那么最小的

\frac{cost+X}{F}

就可以三分来求。

O(n^2m+q\log n)

。

上一篇：21.2.22 总结

下一篇：线性规划和对偶问题_学习笔记

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！