最大网络流算法

参考题目HDU 3549 这是一个裸题，给定流网络，直接求最大网络流。

什么是网络流？

  设流网络$G=(V,E)$是一个有向图，图中每条边$(u,v)\in E$有一个非负容量值$c(u,v)\ge 0$。在所有结点中存在两个特殊结点：源节点$s$和汇结点$t$；源节点只出不进，汇结点只进不出。为方便起见，假设每个结点都在源节点到汇结点的某条路径上，即存在路径s~v ~t。因此流网络是连通的，并且除源节点外每个结点至少有一条进入的边。   对于一个流网络，设$f(u,v)$为边$(u,v)$上的流量，其值应当满足以下性质：

容量限制：$f(u,v)\le c(u,v)$，即边上的流量小于该边的容量斜对称性：$f(u,v)=-f(v,u)$，比如说，从$u$到$v$流入了3，相当于从$v$到$u$流入了-3的流量。流量守恒：对于所有的除源点s和汇点t外的结点，$\sum f(u,v)=0$，即流入某一点的流量等于流出该点的流量，类似基尔霍夫定律。

最大网络流

  最大网络流的求解目的就是给定流网络，求从源点s到汇点t的最大流量，即汇点t处能获得的最大流量。同时在求解过程中要满足流量的三个性质。   求解方法就是通过广度搜索BFS寻找一条有效路径$L$（路径上各边的容量都严格大于0称为有效路径），然后找到这条路径上的最小残量的一条边,残量定义为$c(u,v)-f(u,v)$，设其值为$res(u^{{}^{\prime }},v^{{}^{\prime }})$。由于流量限制，一条路径上的最大流量是由最小容量边决定的。然后将该路径上每条边的流量都加上这个最小值，显然，加上这个值后，该路径所有边流量都不会超过容量。   即更新流网络，$f(u,v)=f(u,v)+res(u^{{}^{\prime }},v^{{}^{\prime }})((u,v)\in L)$，那么在下次求残量的时候就相当于每条边容量减小了$res(u^{{}^{\prime }},v^{{}^{\prime }})$。更新后的网络就叫做残量网络。寻找有效路径的过程叫做找增广路经，即找到一条增广路径就意味着路径上的流量还可以增加$res(u^{{}^{\prime }},v^{{}^{\prime }})$，即当前结果并不是最优，汇点总流量还可以增加$res(u^{{}^{\prime }},v^{{}^{\prime }})$，因此最大流问题就是不断寻找增广路径，不断增加汇点流量，直到找不到一条增广路径时，此时获得的流量即为最大流。   但是，还存在一个问题，就是更新了残量网络可能并不能达到最优，比如下面的例子（边上的数字表示该边的容量）   对于此图如果找到1-2-3-4的路径，更新网络后为如下所示（边上的数字表示减去残量后的容量，即0表示该边不能再由流量经过） 此时汇点获得的流量为1，可以发现不能再找到一条增广路径了，因为2-3容量变为0，但是我们知道，从一开始走1-2-4和1-3-4两条路径可以有更大的最大流2，因此在此，我们要在更新网络后能够有反悔的机会，即让2-3这条边还能反向走，所以引入了反向边   对反向边可以这样理解，以上面的例子为例，开始走1-2-3-4这条路径后，2-3边容量为0，流量为1（注：图中的边上的数字表示容量，但实际计算或者代码实现的时候容量保持不变，更新的是流量$f(u,v)$），然后现在我们试着走1-3-2-4这条路径，在3-2时，假设能够从3走到2，那么相当于抵消掉了原来2-3中的流量，此时2-3这条边的流量为0；然后2-4中有了单位1的流量，其实就相当于将原来2-3中的流量退回去，又送到了2-4中，而更新后3-4中的流量相当于来源于1-3中的流量，这样就很好理解了。现在我们重新来看一下上面那个例子： 首先找到第一条增广路径1-2-3-4（蓝色线所示） 然后更新各边容量（为方便起见，图中都是对容量更新，流量更新转换一下就是了）棕色线是反向容量的更新，正向容量是减，反向容量就是加，如下图： 现在可以发现，1-3-2-4这条路与开始1-2-3-4路径上的流量一致，其实正向边、反向边都是相对而言的，并没有绝对的正向与反向。于是这条路就可行，下面是按路径1-3-2-4路径走完后更新的残量网络：   现在我们可以发现，所有能到达汇点4的路径由于容量限制，不再有增广路径，此时汇点获得的流量为最大流。对于中间2-3和3-2这两条边来说，目前更新后是以3-2为正向，所以3-2容量为0，已经流满，同时反向的容量为1，也表示流满（因为反向边初始容量为0，后面将会说明），那么正反向就互相抵消，即2-3这条路中没有流量，这跟初始状态的2、3边情况是一样的。   那么具体如何来实现呢？可以对每次更新残量网络的时候进行正反两条边的更新，那么算法可以描述为：

$dowhile$    找到一条增广路径$L$，路径上每条边满足流量三个性质    找到最小残量 $res(u^{{}^{\prime }},v^{{}^{\prime }})=min\{c(u,v)-f(u,v)|(u,v)\in L\}$    更新$L$上每条边，得到残量网络：        正向边：$f(u,v)=f(u,v)+res(u^{{}^{\prime }},v^{{}^{\prime }})$        反向边：$f(v,u)=f(v,u)-res(u^{{}^{\prime }},v^{{}^{\prime }})$    $maxflow=maxflow+res(u^{{}^{\prime }},v^{{}^{\prime }})$$until$找不到增广路径$print(maxflow)$//输出最大流     在初始化的时候，对于所有正向边和反向边的流量初始化为0，因为开始没有任何流量流通。即$initial:f(u,v)=f(v,u)=0$显然，满足流量三个性质。然后更新的时候，正向边加上残量，流量变为正，反向边减去残量，变为负，显然，加上的和减去的是相同的值，所以满足斜对称性。值得注意的是，正向边的容量上限是$c(u,v)$，而反向边容量上限是0，所以在初始化容量时，有：     正向边：$c(u,v)=c$     反向边：$c(v,u)=0$ 当然，在寻找最小残量是公式统一都是$$res=min(res,c(u,v)-f(u,v))$$因为即使是反向边，由于容量为0，流量为负数，相减也会得到一个正数。   在寻找增广路径的时候，主要采用的是BFS搜索，当然DFS也可以，但据说大多数情况下BFS更优。下面是C++代码实现，也是例题HDU 3549的AC代码，这里运用了一个pre[i]前驱数组，用来保存i结点的前一个结点，方便在每找到一条增广路径后返回去遍历这条路径，进行各边的更新。 #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define inf 0xfffffff using namespace std; int cap[305][305];//容量 int pre[305];//记录前驱结点 int flow[305][305];//流量 int res[305];//残量 int N,M; queue<int>Q; int MaxFlow() { int sumflow=0; memset(flow,0,sizeof(flow)); memset(pre,0,sizeof(pre)); while(1) { memset(res,0,sizeof(res));//每一次增广都要初始残量为0 res[1]=inf; while(!Q.empty())Q.pop(); Q.push(1); while(!Q.empty())//BFS搜索 { int f=Q.front();//获取队头 Q.pop();//队头出队 if(f==N)break; //找到目标点即汇点N，结束本次增广 for(int i=1;i<=N;i++) { if(!res[i]&&cap[f][i]>flow[f][i])//容量大于流量 { //这里要求容量严格大于流量，所以更新后的残量 //一定大于0，所以res[]也起标记是否访问的作用 res[i]=min(res[f],cap[f][i]-flow[f][i]); //取最小残量 pre[i]=f;//保存前驱结点 Q.push(i);//入队 } } } if(res[N]==0)//到汇点的所有路径最小残量为0 return sumflow;//无法继续更新最大流量 //即当前获得的流量为最大流，直接返回 int k=N,p; while(k!=1) {//利用前驱结点数组，遍历增广路径 //更新增广路径上每条边的流量 p=pre[k]; flow[p][k]+=res[N];//正向边加上残量 flow[k][p]-=res[N];//反向边减去残量 k=p; } sumflow+=res[N];//更新总流量 } } int main() { ios::sync_with_stdio(false); int t,k=0; cin>>t; while(t--) { memset(cap,0,sizeof(cap));//初始容量为0 cin>>N>>M; for(int i=0;i<M;i++) { int x,y,c; cin>>x>>y>>c; cap[x][y]+=c;//初始正向容量 } cout<<"Case "<<++k<<": "<<MaxFlow()<<endl; } return 0; }