欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

上下界网络流 (更新中)

程序员文章站 2022-06-10 14:45:59
...

最近刚学了上下界网络流,写篇博客梳理下知识。
大佬的博客: https://oi.men.ci/network-flow-with-bounds/

何为上下界网络流? 其和普通的网络流的区别就在于每条边的流量不仅有上界,同时还有一个下界,普通网络流的下界是0

无源无汇上下界可行流

问题: 给出一个上下界网络流图,问是否存在一条可行流。

做法:添加超级源点S,超级汇点T,这里对边进行拆解,对于一条容量为[low,high](u,v)边,可以知道v一定会流入low的流量,根据流量平衡,u一定要流出low的流量。那么我们可以直接从S连一条容量为low的边到v,从u连一条容量为low的边到T,这样就可以满足其下界的条件,这时候(u,v)之间就变成了容量为[0,high-low]的边。这个问题就转化成了普通的有源汇网络流问题。那么是否由可行流呢?我们构建完这个图后,ST的最大流如果满足所有从S连向外面的边的总容量那么就存在可行流。
为什么呢? 因为我们构图的时候,从S连出的边的容量是其下界,是一定要满足的!所以必须要满流。
上下界网络流 (更新中)

这样建边的话,每条边会多出两条边。考虑下优化。
上下界网络流 (更新中)
对于如图所示的情况:
注意这是可行流,你只需判断是否有流量能在这张图上流动就可以了!

  1. 如果 x < y,那么S一定有x的流量可以流向y,这条边一定可以满流,所以就没有作用了,于是删除,然后改造(i,T),因为已经流了x的流量了,所以这条边变成(y-x)即可。
  2. 如果x > y,那么对于(i,T)这条边可以满流,所以没有作用了,于是删除(i,T),然后改造SS只要多流x-y的流量到i然后经过其他边到T即可。

这里只是列出一个点的情况,所以删除掉边之后就没有流了,是不可行的。(你想想一个点流个蛇皮的网络流哦)

真实情况是有非常多个点,非常多个边,改造后的边的流量是会经过其他点边流的。可以自己多画几个点看看。

根据上面所述,一个点只要知道流入的流量和流出的流量差值即可建边,那么可以用一个数组extra[i]表示差值。
对应hdu4940

		memset(extra,0,sizeof extra);
		int u,v,d,b;
		int S = 0, T = n+1;
		int sum = 0;
		for(int i = 0; i < m; ++i) {
			scanf("%d%d%d%d", &u, &v, &d, &b);
			//b = d+b;
			dinic.add(u,v,b); // b = d+b-d
			extra[v] += d;
			extra[u] -= d;
		}
		for(int i = 1; i <= n; ++i) {
			if(extra[i] > 0) {
				sum += extra[i];
				dinic.add(S,i,extra[i]);
			} else if(extra[i] < 0)
				dinic.add(i,T,-extra[i]);
		}