概述
用网络流来解决线性规划问题。这样的好处是思维量较小,只要做代数变换就可以建图,而不用考虑建图的实际意义。
核心思想就是利用流量守恒来使你要最优化的一个线性规划的函数。这样比较抽象,具体的来说,就是利用流量守恒的性质条件来满足一个方程组。
主要的步骤有三个
- 列出不等式,通过增加或减少一个量使得不等式变为等式。
- 通过代数变换使得一组等式中的元仅仅出现于两个方程中,并且一个系数为正,一个系数为负。这样可以通过加减消元来解方程 (重点
- 根据题目条件按照特定方法建图
例题
来一道入门题来了解一下,因为我更博太难得了,所以放在题解里讲
建模
通过该题,应该已经对这种模型的建模方法有了了解。现在,我们将该方法推广至更一般性的问题。
首先通过例题我们已经知道了,
把每个方程看作一个点,把元看成边。那么系数为负的元作为出边流出一个方程组,系数为正的元入边流入作为方程组。能解出这样的元,当且仅当等式为$0$,也就是流量守恒(平衡。容量为变量的上下界,费用就是题目给你的费用。
对于常数项,我们可以通过源点和汇点来解决。设右边的常数项为$d$,若$d > 0$ ,则从$s$向该方程连边。否则,该方程连一条边到汇点。容量均为$inf$,费用为$$0$
我们先来提炼一下,首先构造方程组,我们的唯一要求是:
每个变量在方程组中出现恰好两次,且符号相反
注意,通过差分的方法可以更方便地变换出这样的方程组,且可以使系数的绝对值均为$1$来方便我们解决问题。这是很好的性质。
第二步,把方程看成点,把变量建成边。符号为负的看作出边,符号为正的看作入边。点的流量平衡(方程为$0$)就是方程左边满足的情况。注意,该处说的方程指的是点的流量方程。
然后,如何确定边的容量和费用?容量的上下界就是变量的上下界,费用是可以求题目的答案,或者就是题目给你的费用(因题而异,出现这种题目给你了费用的还是比较容易)
最后,怎么处理方程右边的常数项?按照常数项的正负,分别流出源点、流入汇点即可。
至此,不等式建模的有关的题,全部能够通过上述方法一一解决!!!!!!!!!!!!!!!!!!!!!!!!!
- 说明遇到了强大的对手,例如题目还有些其他的限制要满足,或者别的牛逼性质可以利用。这种情况请考虑加上其他建模技巧来配合不等式模型,不要硬刚一种技巧和模型。
- 这题确实牛逼,可能真的要用到什么单纯形法之类的。这种情况你来找我,第一我有足够自信我上面讲的基本适用所有题目。第二如果这题真牛逼,要么我来扩展我上面所讲,要么我去请隔壁或者直接请数学组WZH来奖讲这东西。
加强版题目
基本上上面讲了的方法这里面全部用了,有时间我会写题解的。现在太晚了,已经凌晨一点了。
坑点
- 你建边的时候请注意一下边的顺序,如果你发现你最小费用最大流跑出来的最小费用是个负的,要么你把你边的流入和流出对调,要么直接改成
minCost -= k *edge[i].w
- 请在用spfa跑残量网络的时候,返回的时候请写
return dis[t] != dis[0]
- 注意你差分的时候$0$和$n+1$的方程,源点汇点设置要注意(但是像我这种直接把源点汇点直接连很远的就不会有问题
如果这些问题你debug的时候都没出现只能说明你代码真牛逼
此外,一定要注意了。这个模型转换后的本质是解决线性规划问题的,切不可认为解这样的方程组跟高斯消元没啥区别