关于有源汇上下界最小流
本篇仅记录作者自己关于这个知识点的理解,在大佬看来可能很 naive 吧。
在 xht 大佬关于 P4843 清理雪道 的题解中,有一种特别的求出最小流的方式,优越性可能是好背,利用了一些 \(\operatorname{Dinic}\) 的性质,在此简单记录。
做法
定义源汇分别为 \(s,t\),以及为平衡流量而制造的超级源,超级汇。
我们首先在建出的网络流图上对于超级源到超级汇跑一次最大流,尽可能满足流量平衡。
若此时已平衡,则无需让 \(s\to t\) 之间有额外的流量,答案为 \(0\)。实现中并不需要特判。
然后,我们从建立一条从 \(t\) 到 \(s\),流量为 \([0,+\infin)\) 的边,再跑一次最大流(超级源到超级汇),这条边上面的流量就是我们要求的最小流。
解释&理解:
首先需要弄清楚一件事,从 \(t\) 向 \(s\) 连的一条 \([0,+\infin)\) 上的流量就是 \(s\) 到 \(t\) 的流量。
然后,我们需要解决两个问题:为什么最小,以及,为什么合法。
对于某些点,他们拥有来自超级源的流量,但是并不一定能够全部流向超级汇;对于另外一些点,他们需要向超级汇输送流量,但是不一定足够。在跑完最大流后,不足或是溢出的流量数一定最少。如果存在一种从 \(s\) 到 \(t\) 的流法,使得满足流量守恒,那么,淤积的流量一定应该从 \(t\) 流走,不足的流量一定会从 \(s\) 补充,这两部分流量必定相等!
- 淤积的流量一定应该从 \(t\) 流走,不足的流量一定会从 \(s\) 补充:
- 考虑普通网络流的过程其实就是给 \(s\) 无限流量并查询能到达 \(t\) 的流量的最大值,所以,这些从 \(s\) 补充,从 \(t\) 流走是合理的。
- 这两部分流量相等:
- 这个倒是显然,恐怕无法建出不相等的图吧。
- 注意:在有源汇上下界最小流中,并不一定所有边上的流量都是来自源点,流向汇点的,他们可以
内部消耗因环流而合法。我们不认为环流需要消耗流量。
根据上述 1,2 我们就能得到“从 \(t\) 向 \(s\) 连的一条 \([0,+\infin)\) 上的流量就是 \(s\) 到 \(t\) 的流量”这个结论,因为多流走的将流向 \(s\) 并弥补不够的部分,完全可以视作从 \(s\) 流向 \(t\)。
又因为,我们在之前的最大流中,已经尽量满足了下界(需要超过上界的根本原因,还是无法满足下界,所以只讨论无法满足下界的情况)并且完全流满了环流(此处利用了 \(\operatorname{Dinic}\) 的性质,一定会增广到无法增广为止),我们只需要 \(s\to t\) 的流量中给整张图再添加最小的流量(\(\operatorname{Dinic}\) 一定每次找最短的增广路进行增广,回流一定不是最短的增广方式,也不会增加流量了),从而满足整张图的的需求,由此,最小的性质和合法的性质均已得到证明。
标签:增广,有源,超级,最小,流量,下界,汇上 From: https://www.cnblogs.com/lazytag/p/17001989.html