不等关系建模总结

博主： tony102
发布时间：2021 年 02 月 27 日
1507 次浏览
暂无评论
1614字数
分类：总结

## 概述

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

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

主要的步骤有三个

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

## 例题

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

## 建模

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

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

>   把每个方程看作一个点，把元看成边。那么系数为负的元作为出边流出一个方程组，系数为正的元入边流入作为方程组。能解出这样的元，当且仅当等式为$0$，也就是流量守恒（平衡。容量为变量的上下界，费用就是题目给你的费用。
>
>   对于常数项，我们可以通过源点和汇点来解决。设右边的常数项为$d$，若$d > 0$ ，则从$s$向该方程连边。否则，该方程连一条边到汇点。容量均为$inf$，费用为$$0$

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

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

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

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

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

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

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

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

## 加强版题目

[LOJ6079. 「2017 山东一轮集训 Day7」养猫](https://loj.ac/p/6079)

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

## 坑点

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

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

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

最后修改：2021 年 08 月 20 日