线性规划

发布时间 2023-12-01 23:22:47作者: atarashiTLE

不懂就死记。

对于边$(u,v)\in V , c_{u,v} $为它的最大流量$,b_u$为u的流量需求(流向汇点的流量)(必须为它),$w_{u,v}$为费用,求:
$$\text{min}\sum_u b_up_u + \sum_{u,v} c_{u,v}\text{max}(0,p_v-p_u-w_{u,v})$$

其中,$p_u$为变量。($\sum_v f_{v,u}-\sum_v f_{u,v}$的对偶变量)。

ref.[dxm论文](https://rusunoi.github.io/books/National-Team-Thesis/2021.pdf)。

简单证明:[there](https://www.cnblogs.com/whx1003/p/15512684.html)