[数据结构与算法]有上下界网络流问题汇总

无源汇上下界可行流

这是这个问题的基石

我们不妨进行一个对比, 对比经典网络流与现在的无源汇上下界可行流的区别, 显然, 最终的解法是要向经典网络流靠近的. 我们就看看, 怎么用经典算法, 解决新问题.

设$f(u,v)$为从u到v的流量, 若边的流量限定为$[L,R]$, 那我们定义$b(u,v)=L$为边的最小流量, $c(u,v)=R$为边的最大流量. 然后, 请看下表

$$\begin{array}{ccc}& 经典网络流& 无源汇上下界可行流\\ & & \\ 流量限制& f(u,v)\in [0,c(u,v)]& f(u,v)\in [b(u,v),c(u,v)]\\ & & \\ 流量平衡& \sum f(u,i)=\sum f(i,v)& \sum f(u,i)=\sum f(i,v)\end{array}$$
可以看到，“流量平衡”是两者的共同点，也是所有网络流问题内含的一个必然要求。

而不同点在于多了个下界，只要把下界一消，二者就和同为一家聊。怎么消掉下界呢？

我想起前几天我碰到的一道隔板法的题目,
经典的隔板法问题, 是n个糖果, m个小朋友分, 每个人至少一个糖果, 那么方案数是$\left(\genfrac{}{}{0ex}{}{n?1}{m?1}\right)$.
但我的这题的小朋友没那么善良, 大家都很自私, 会出现有人没有糖果的情况.
遇到这样的变式, 当然难不倒我, 我调用我全部高中之所学, 缓缓写下一道公式$y=x+1,令y\ge 1,则x\ge 0$.我们把现在的y拿去做隔板法, 假设有这么一个方案y1,y2,y3,…,yn, 那么实际情况就是y1-1,y2-1,y3-1,…,yn-1, 诶嘿, 这下就满足要求了. ${\sum }_{i=m}^n{y}_i={\sum }_{i=1}^m{x}_i+m=n+m$, 应该是$\left(\genfrac{}{}{0ex}{}{n+m?1}{m?1}\right)$.
即先多放n块空的糖纸进去, 以假乱真.

同样的道理, 这次的无源汇上下界可行流依然可以采用类似的思想.

既然经典是解决[0,R]的问题的,而我们的区间是[L,R], 不妨, 变成[0,R-L]？？？机会来了！！！把那L块糖果给拿出来！

然后围绕此, 我们对这条边进行增增补补, 以保证“流量平衡”依旧成立。想做到这一点，我们想，一个点如果流出一条[L,R]，我么会将其改造为[0,L-R]，那么这个点将少流出L的流量。这时候，如果我们给它再流L的流量进来，那不就完美啦。设立一个超级源点，连接它，流量为L。这样就OK了。如果是流出少了，就让它流到超级汇点。

总而言之，解决此类问题，关键要保证其“流量平衡”成立。统计每个点流入和流出的下限，流入作正，流出作负，我将其称为度。$du[x]=in[x]?out[x]$。如果du[x]最终为正，从源点向它连一条du[x]的边；如果为负那么连向汇点-du[x]。

回到问题上来，怎么判断可行与否?你想，我们限制了每条边的流量是[0,R-L]这里是出不了什么岔子的，但是我们是在假定它的基础流量为L的情况下的哦，这个基础流量能不能满足呢？想要检验这个问题，等价于我们要让刚刚额外建的这些边满流。这个可以理解吧，因为这些用du建成的额外边，是所有边的总和。

要考虑是否满流，拿出经典网络流就可以了，从超级源点出发跑一次到超级汇点的最大流，这就是做法。

所以，最终的检验条件是，判断超级源点的出边的流量，是否等于所有入额外边的容量和，等则存在可行方案；不等，不可行。这个检验条件当然等价于去检验超级汇点入边的流量，与所有出额外边的容量和。

跑完给出一个方案，所有边取：边的流量+下限L。即可

最终答案= maxflow(SS,TT)==额外边入边和？

有源汇上下界可行流

有源汇上下界可行流的解法考虑用刚刚解决的无源汇上下界可行流。

怎么同化呢？设法让这张有源汇上下界可行流变成一张无源汇上下界可行流，同时要求“流量守恒”这是万年不变的规矩了。

想想想想，解法很简单！！(设S是源点，T是汇点)就是建立一条T->S容量为$\infty$的边。你想嘛，S是不是可以无限地制造流量？T是不是可以无限地接受流量？整张图就他俩不满足流量守恒！要想让他们束手就擒，我们就让S流出了多少，就流回自己多少，通过把T和S连接起来，成功解决了这个问题。

剩下的，就和无源汇上下界可行流一模一样了。

最终答案= 连接S->T后maxflow(SS,TT)==额外边入边和？

有源汇上下界最大流

好的，看到第三个问题了。要解决它，我们发现和第二个问题很像，就是要求了个最大而已。想要搞清楚第三个问题解法的原因，还得细细地来研究第一个问题。

上回讲到，从SS(超级源点)跑一个最大流到TT(超级汇点)就完事。第二个问题中，加入了S(源点)和T(汇点)后依旧如此。其实我们在解第一个问题的时候，并不关心S和T究竟在哪里。我们跑一次SS到TT的最大流，纯粹是为了验证是否能让所有“新加的边都满流”。

留意跑完这个最大流后的残余网络，是个什么？这个问题灰常关键，经常我们都只顾着做答案，而忽视了残余网络也是一个很有用的东西。它是除去了下限流量后的网络！可以理解成刚才导致流量不平衡的那些边，现在都已经被消除掉了。刚才是假想的一张经典网络最大流图，现在是真的了，同时还得到了一部分S到T的流量。你可以理解成是用用下限去跑的，有点像在每条边的容量为[0,L]去求的解。

上面是答案的一部分，考虑到还有一些边是为和SS和TT连边的，而且刚刚也只是跑了一个下限流量，我们还得明确S和T再跑一次最大流。注意此时已经消去了下限的影响，就是说它就是一个普普通通的最大流，所以别忘了把之前为了转换成无源汇时连接的T->S的边删掉哦。

最终答案= 连接S->T后maxflow(SS,TT) 中从S出发流到T的流量 + 删掉T->S后maxflow(S,T)

模板(洛谷P5192 Zoj3229 Shoot the Bullet|东方文花帖|)

#include<bits/stdc++.h>
using namespace std;
const int INF=999999999;
const int N=375,M=1010,C=305;

struct E{int y,c,next;}e[((N+N*C+M)+(N+M))*2];int len,last[N+M];
void ins(int x,int y,int c)
{
	e[++len]=(E){y,c,last[x]};last[x]=len;
	e[++len]=(E){x,0,last[y]};last[y]=len;
}

struct DINIC
{
	int st,ed;
	int h[N+M];
	int list[N+M];int head,tail;
	
	bool bfs()
	{
		memset(h,0,sizeof h);h[st]=1;
		head=0;tail=1;list[0]=st;
		while(head<tail)
		{
			int x=list[head++];
			for(int k=last[x];k;k=e[k].next)
			{
				int y=e[k].y;
				if(e[k].c && !h[y])
				{
					h[y]=h[x]+1;
					list[tail++]=y;
				}
			}
		}
		return h[ed];
	}
	
	int dfs(int x,int flow)
	{
		if(x==ed) return flow;
		int res=flow;
		for(int k=last[x];k;k=e[k].next)
		{
			int y=e[k].y;
			if(h[x]+1==h[y] && e[k].c)
			{
				int tmp=dfs(y,min(res,e[k].c));
				res-=tmp;
				e[k].c-=tmp;e[k^1].c+=tmp;
				if(!res) break;
			}
		}
		if(res==flow) h[x]=0;
		return flow-res;
	}
	
	int Dinic(int sstt,int eedd)
	{
		st=sstt;ed=eedd;
		int ans=0;
		while(bfs()) ans+=dfs(st,INF);
		return ans;
	}
}sol;

int S,T,SS,TT;
int du[N+M];

void init()
{
	len=1;
	memset(last,0,sizeof last);
	memset(du,0,sizeof du);
}

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		S=n+m+1;T=S+1;SS=T+1;TT=SS+1;
		ins(T,S,INF);
		for(int i=1;i<=m;i++)
		{
			int g;scanf("%d",&g);
			ins(i,T,INF-g);//[g,INF] debug
			du[i]-=g;du[T]+=g;//in:-  out:+ 
		}
		for(int i=1;i<=n;i++)
		{
			int day=m+i;
			int c,d;scanf("%d%d",&c,&d);
			ins(S,day,d);//[0,d]
			for(int j=1;j<=c;j++)
			{
				int t,l,r;scanf("%d%d%d",&t,&l,&r);t++;//注意编号女孩编号从0开始
				ins(day,t,r-l);//[l,r]
				du[day]-=l;du[t]+=l;
			}
		}
		int flag=0;
		for(int i=1;i<=T;i++)
		{
			if(du[i]>0) ins(SS,i,du[i]),flag+=du[i];//flag在这里计数
			else if(du[i]<0) ins(i,TT,-du[i]);//noteic: -du[i]
		}
		
		if(sol.Dinic(SS,TT)!=flag)//判断附加边是否满流
		{
			puts("-1\n");
			continue;
		}
		int ans=e[3].c;//第一部分答案
		e[2].c=e[3].c=0;//切断(T,S,INF)
		ans+=sol.Dinic(S,T);//第二部分答案
		printf("%d\n\n",ans);
	}
	return 0;
}

有源汇上下界最小流

利用反向边的特点，把利用率不足的流量再用起来。删掉T->S后，仍然在残留网络上，从T到S跑一次最大流，求一下最多能少多少。

问题：会不会使流量缩减到不满足流量下限?

不会.和有源汇有上下限的最大流一样,我们之前从每条边上拿出了大小等于流量下限的流量构成初始流,这些流量不在我们建出的图中.最极端的情况是缩减到所有边的流量等于流量下限,不会更小了.

最终答案= 连接S->T后maxflow(SS,TT) 中从S出发流到T的流量 - 删掉T->S后maxflow(T,S)