概述

用网络流来解决线性规划问题。这样的好处是思维量较小,只要做代数变换就可以建图,而不用考虑建图的实际意义。

核心思想就是利用流量守恒来使你要最优化的一个线性规划的函数。这样比较抽象,具体的来说,就是利用流量守恒的性质条件来满足一个方程组。

主要的步骤有三个

  1. 列出不等式,通过增加或减少一个量使得不等式变为等式。
  2. 通过代数变换使得一组等式中的元仅仅出现于两个方程中,并且一个系数为正,一个系数为负。这样可以通过加减消元来解方程 (重点
  3. 根据题目条件按照特定方法建图

例题

来一道入门题来了解一下,因为我更博太难得了,所以放在题解里讲

建模

通过该题,应该已经对这种模型的建模方法有了了解。现在,我们将该方法推广至更一般性的问题。

首先通过例题我们已经知道了,

把每个方程看作一个点,把元看成边。那么系数为负的元作为出边流出一个方程组,系数为正的元入边流入作为方程组。能解出这样的元,当且仅当等式为$0$,也就是流量守恒(平衡。容量为变量的上下界,费用就是题目给你的费用。

对于常数项,我们可以通过源点和汇点来解决。设右边的常数项为$d$,若$d > 0$ ,则从$s$向该方程连边。否则,该方程连一条边到汇点。容量均为$inf$,费用为$$0$

我们先来提炼一下,首先构造方程组,我们的唯一要求是:

每个变量在方程组中出现恰好两次,且符号相反

注意,通过差分的方法可以更方便地变换出这样的方程组,且可以使系数的绝对值均为$1$来方便我们解决问题。这是很好的性质。

第二步,把方程看成点,把变量建成边。符号为负的看作出边,符号为正的看作入边。点的流量平衡(方程为$0$)就是方程左边满足的情况。注意,该处说的方程指的是点的流量方程。

然后,如何确定边的容量和费用?容量的上下界就是变量的上下界,费用是可以求题目的答案,或者就是题目给你的费用(因题而异,出现这种题目给你了费用的还是比较容易)

最后,怎么处理方程右边的常数项?按照常数项的正负,分别流出源点、流入汇点即可。

至此,不等式建模的有关的题,全部能够通过上述方法一一解决!!!!!!!!!!!!!!!!!!!!!!!!!

  1. 说明遇到了强大的对手,例如题目还有些其他的限制要满足,或者别的牛逼性质可以利用。这种情况请考虑加上其他建模技巧来配合不等式模型,不要硬刚一种技巧和模型。
  2. 这题确实牛逼,可能真的要用到什么单纯形法之类的。这种情况你来找我,第一我有足够自信我上面讲的基本适用所有题目。第二如果这题真牛逼,要么我来扩展我上面所讲,要么我去请隔壁或者直接请数学组WZH来奖讲这东西。

加强版题目

LOJ6079. 「2017 山东一轮集训 Day7」养猫

基本上上面讲了的方法这里面全部用了,有时间我会写题解的。现在太晚了,已经凌晨一点了。

坑点

  1. 你建边的时候请注意一下边的顺序,如果你发现你最小费用最大流跑出来的最小费用是个负的,要么你把你边的流入和流出对调,要么直接改成minCost -= k *edge[i].w
  2. 请在用spfa跑残量网络的时候,返回的时候请写 return dis[t] != dis[0]
  3. 注意你差分的时候$0$和$n+1$的方程,源点汇点设置要注意(但是像我这种直接把源点汇点直接连很远的就不会有问题

如果这些问题你debug的时候都没出现只能说明你代码真牛逼

此外,一定要注意了。这个模型转换后的本质是解决线性规划问题的,切不可认为解这样的方程组跟高斯消元没啥区别

最后修改:2021 年 08 月 20 日
如果觉得我的文章对你有用,请随意赞赏