摘要： 最大流可以看做是把一些东西从源点s送到汇点t，可以从其他的点中转，每条边最多只能输送一定的物品，求最多可以把多少东西从s送到t，这样的问题就是最大流问题。
最大流可以看做是把一些东西从源点s送到汇点t，可以从其他的点中转，每条边最多只能输送一定的物品，求最多可以把多少东西从s送到t，这样的问题就是最大流问题。
节点1为源点，节点5位汇点
每一条边上的数字即为这条边最多能输送的数量，也称为容量。（对于不存在的边，容量为0）
这个图能够求出的最大流为24。
这时，实际运送的物品量即为流量。
有些边的流量不一定等于容量，也就是还可以在这条路上再流多几个物品，这时，容量减去流量的值，即为残量
残量会单独构成网络，但不一定联通s和t，这样的网络称作残量网络。
那么，应该怎么求最大流呢？
这里介绍一个最基础的算法，增广路算法。
在图上，从s开始，任意取一条路来走，走到t，增加流量。重复这样的操作。但是很快，我们可以发现，这样的做法不一定是最优的做法。所以，我们要给它一个改进的机会。
在图上建立反向弧，将容量设置为0，当从节点u流向节点v时，反向弧的流量也相应等于这条弧的流量的相反数。
那么，通过搜索，每一次寻找一条路径，使得流向汇点的总流量增加，这个过程叫做增广，走过的路为增广路。
可以证明，通过这个过程，经过多次的增广，必然会陷入不能增广的情况，这时，流向汇点的总流量即为最大流。
只要残量网络中s和t是连通的，必然会得到一条增广路径。
找路径最简单的办法就是用DFS，但是对于一些具有刁钻数据的网络流题目，DFS可能会空间溢出或者超时，所以使用到BFS，也就是题目中说的Edmonds-Karp算法。
代码模板（来自算法竞赛入门第二版（刘汝佳））：
structedge{intfrom,to,cap,flow; edge(intu,intv,intc,intf):from(u),to(v),cap(c),flow(f){}};structEdmonds_Karp{intn,m;vectoredges;//边数的两倍vectorg[maxn];//邻接表，g[i][j]表示节点i的第j条边在e数组中的序号inta[maxn];//当起点到i的可改进量intp[maxn];//最短路树上p的入弧编号voidinit(intn){for(inti=0;iq; q.push(s); a[s]=inf;while(!q.empty()){intx=q.front();q.pop();for(inti=0;i<(int)g[x].size();i++){ edge&e=edges[g[x][i]];if(!a[e.to]&&e.cap>e.flow){ p[e.to]=g[x][i]; a[e.to]=min(a[x],e.cap-e.flow); q.push(e.to); } }if(a[t])break; }if(!a[t])break;for(intu=t;u!=s;u=edges[p[u]].from){ edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } flow+=a[t]; }returnflow; }}EK;
版权声明：本文内容由互联网用户自发贡献，版权归作者所有，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至：yqgroup@service.aliyun.com 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
用云栖社区APP，舒服~
