《网络流学习笔记01》

《网络流学习笔记01》

1.网络流初步。

网络流是一个适用范围相当广泛的模型，相关的算法也很多，这里就几天学习网络流的相关知识做一个总结归纳。

（1）最大流问题

如图所示，假设你需要把一些物品从结点s（称为源点）运送到结点t（称为汇点），可以从其他结点中转，图（a）中各条有向边的权表示最多能有多少个物品从这条边的起点直接运送到终点，例如图（a）从结点V3到V2最多可以运送9个物品。

图（b）给出了一种可能的最优方案，其中每条边中的第一个数字表示实际运送的物品数量，第二个数字表示题目中的上限，

我们把求解这样的问题称为最大流问题（Maximum-Flow Problem）。对于一条边（u,v）它的物品上限称为容量（capacity）,记为c(u,v),（对于不存在的边（u,v）,c(u,v)=0）；实际运送的物品称为流量（flow）,记为f(u,v)。注意：“如果把3个物品从结点u运送到结点v,有把5个物品从v运送到u”等价于把两个物品从v运送到u,

这样，我们就可以定义f(u,v)和f(v,u)最多只有一个正数（可以均为0），并且f(u,v)=-f(v,u)。这样规定就好比“把m个物品从u运送到v“等价于“把”-m个物品从v运送到u”一样。

注意：

在最大流问题中，容量c和流量f满足3个性质：容量限制（f(u,v)<=c(u,v)），斜对称性（f(u,v)=-f(v,u)）,流量平衡（对于除了结点s和t外的任意结点u

）

即：

1.增广路算法

介绍完最大流问题后，接下来给出求解问题的方法。算法思路也很简单，从零流（所有边的流量为0）开始不断增加流量，保持每次增加流量后都满足容量限制，斜对称性和流量平衡3个条件，

把图（a）中的每条边上容量与流量之差（称为残余容量，简称残量）计算出，得到图（b）的残量网络（rasidual network）。同理，有图（c）可得到图（d）,注意残量网络中的边数可能达到原图中的两倍，如原图中c=16,f=11。

上述算法基于这样一个事实：残量网络中任何一条从s到t的有向路都对应一条原图中的增广路（augmenting path）-只要求出改条道路中所有残量的最小值d，把对应的所有边上的流量增加d即可，这个过程称为增广（augmenting）。不难验证，如果增广前的流量满足3个条件，增广路仍然满足，显然，只要残量网络中存在增广路，流量就可以增大

同理可以证明它的逆命题也成立：如果残量网络中不存在增广路，则当前流就是最大流，这就是增广路定理。

注意：当且仅当残量网络中不存在s-t的有向路（增广路）时，此时的流是从s到t的最大流。

【BFS实现】

bfs足以应对数据不难的网络流问题，这就是Edmonds-Karp算法，下面的代码中，源点和汇点保存在变量s和t中，运行结束后，s-t的净流量保存在变量f中。

queue Q;memset(flow,0,sizeof(flow));int sum=0;for(;;){ memset(a,0,sizeof(a)); a[s]=inf; Q.push(); while(!Q.empty()) //BFS找增广路 { int u=Q.front();Q.pop(); for(int v=1;v<=n;v++) if(!a[v]&&cap[u][v]>flow[u][v]) //找到新结点v { p[v]=u;Q.push(v); //记录v的父亲，并且加入FIFO队列 int ans=cap[u][v]-flow[u][v]; a[v]=a[u]

注意：在扩展结点的同时还需要递推出从s到每个结点i的路径上的最小残量a[i]，则a[t]就是整条s-t道路上的最小残量，另外，由于a[i]一直是正数，可以用它代替原来的vis标识数组，上面的代码初始化流为零，实际只要满足3个限制条件，初始化可行就可以用增广路算法进行增广。

【HDU 3549】入门裸题

题目链接：​​click here​​

【POJ1273】入门题

题目链接：​​http://poj.org/problem?id=1273​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。