首页 > 其他分享 >关于有源汇上下界最小流

关于有源汇上下界最小流

时间:2022-12-24 09:12:48浏览次数:58  
标签:增广 有源 超级 最小 流量 下界 汇上

关于有源汇上下界最小流

本篇仅记录作者自己关于这个知识点的理解,在大佬看来可能很 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\) 补充,这两部分流量必定相等!

  1. 淤积的流量一定应该从 \(t\) 流走,不足的流量一定会从 \(s\) 补充:
    • 考虑普通网络流的过程其实就是给 \(s\) 无限流量并查询能到达 \(t\) 的流量的最大值,所以,这些从 \(s\) 补充,从 \(t\) 流走是合理的。
  2. 这两部分流量相等:
    • 这个倒是显然,恐怕无法建出不相等的图吧。
  3. 注意:在有源汇上下界最小流中,并不一定所有边上的流量都是来自源点,流向汇点的,他们可以内部消耗因环流而合法。我们不认为环流需要消耗流量

根据上述 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

相关文章

  • 2190. 有源汇上下界最小流
    2190.有源汇上下界最小流和最大流差不多首先是判断可行吗最后要把起点和终点调换,然后减去#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongcon......
  • 2189. 有源汇上下界最大流
    2189.有源汇上下界最大流和无源点的思路差不多,只是要跑两次图,先用虚点跑,在用实点跑。(不知道为什么我的ISAP会错)#include<bits/stdc++.h>usingnamespacestd;consti......
  • 无源汇上下界可行流
    无源汇上下界可行流首先把每条边设置为max-min然后计算每个点如果流量守恒,还需要流入多少,或流出多少最后根据这个流入和流出对S和T之间进行建图最后边权就是min+流过的......
  • 上界通配符和下界通配符
    publicstaticvoidmain(String[]args){/*Object:超级父类!User:用户类!Student、Teacher:是User的子类!上界......
  • 2189. 有源汇上下界最大流
    题目链接2189.有源汇上下界最大流给定一个包含\(n\)个点\(m\)条边的有向图,每条边都有一个流量下界和流量上界。给定源点\(S\)和汇点\(T\),求源点到汇点的最大流......
  • 基于块分割及CNN的文档矫正与光照消除方法 (有源码和数据)
    人工智能大数据与深度学习 公众号:datayx主要关注手机摄像头进行文档数字化过程中存在纸张几何形变、相机方向导致的透视形变、光照不均导致的阴影等问题。利用3维建模软件......
  • Android开发之制作圆形头像自定义View,直接引用工具类,加快开发速度。带有源代码学习..
    作者:程序员小冰,Android开发之制作圆形头像自定义View,直接引用工具类,加快开发速度。带有源代码学习大家都知道。现在好多头像都是圆形的,不再是以前的正方形或者长方形。因......
  • 【XSY3890】【hdu5263】平衡大师(二分,上下界网络流)
    不妨令\(k=m-k\),那么题目的意思就是至多删去\(k\)条边。首先二分答案\(t\),然后求最少需要删去多少的边,如果最少需要删去的边\(\leqk\)则合法。在原图中统计每一个......
  • 2.4G有源智能电子学生卡(SI24R2E应用实例)
    今年年初教育部发布的《关于加强中小学生手机管理工作的通知》中提出,学生手机有限带入校园,原则上不得将个人手机带入校园,禁止带入课堂;应设立校内公共电话、建立班主任沟通......
  • 目前最强判别能力的深度人脸识别(文末附有源码)
    计算机视觉研究院专栏作者:Edison_G利用深度卷积神经网络进行大规模人脸识别的特征学习面临的主要挑战之一:设计合适的增强识别能力的损失函数。​CVPR已经告一段落,但是好的文......