本文转自http://chuanwang66.iteye.com/blog/1446977
思考顺序：
先有容量限制c[] --> 有多种可能的网络流f[]
--> 找最大流（流值|f|最大的流）
一、网络流
G=<V,E>为有向图
1. 容量为非负: 如果有向边(u,v) 存在，c(u,v)≥0； 如果有向边(u,v)不存在，c(u,v)=0
2. 网络流：
（1）容量限制：f(u,v)≤c(u,v) ==>
单向流速受限
（2）反对称性：f(u,v)=-f(v,u) ==> 在管道中向不同方向看，水流一面迎面而来，一面向前推我
（3）流守恒性：f(V-s-t,V)=0 ==> A. 中间顶点不存储流（流进=流出）
B. 进入中间顶点的正网络流=离开该点的正网络流
注意：
流守恒性也可以写作f(V,V-s-t)=0，即流入一个顶点的总流为0；
在f(V-s-t,V)或f(V,V-s-t)的中，其中每一元素可以为正可以为负，不要以为不能为负（这是“残留网络”中的限制，网络流不受限）
引理26.1: G=<V,E>是流网络，f是G的一个流。
定义f(X,Y)=∑f(x,y)，x∈X, y∈Y.
（1）任意X⊆V, 则 f(X,X)=0 ==>反对称性: f(u,v)= - f(v,u)
（2）任意X,Y⊆V, 则f(X,Y)=-f(Y,X) ==>（1）的推广
（3）X,Y,Z⊆ V, X∩Y=∅ 则f(X∪Y,Z)=f(X,Z)+f(Y,Z)
二、流值 和 最大流
1. 流f的值|f|=f(s,V)=f(V,t)： 源s送出多少水/汇t喝了多少水
2. 最大流问题： 给出流网络G（源点s，汇点t），希望从中找出流值|f*|最大的流f*， f*称为最大流
三、最大流问题求解
1. 三个理论基础 和 “最大流最小割定理”：
理论一：“残留网络 residual network”
网络流图G ==决定唯一==> 有向边的残留容量cf(u,v)=c(u,v)-f(u,v)
网络流图G ==决定唯一==> G导出的残留网络Gf=<V,Ef>, Ef={(u,v)∈V×V: cf(u,v)>0}
（1）后者（残留网络）由满足条件的前者(残留容量严格＞0的有向边)组成
（2）残留网络中的所有有向边上的残留容量均>0. 如果认为残留容量cf(u,v)是残留网络的（有向）边的权值，则所有权值严格>0，∵不满足介个条件的有向边根本就通不过海选!
理论二：“增广路径 augmenting path”
增广路径p: 残留网络Gf中从源点s到汇点t的一条简单路径。
增广路径p的残留容量： cf(p)=min{cf(u,v): (u,v)在增广路径p上}
理论三：“割 cut”
网络流G的割(S,T)，源点s∈S, 汇点t∈T。从S到T的边称为割边。
最大流最小割定理：
（1）f是G的一个最大流 ==>达到流值|f|=f(s,V)最大
（2）残留网络Gf不包含增广路径 ==>不能再压入正网络流
（3）对G的某个割(S,T) ，存在|f|=c(S,T) ==>对最大流的限制来自最小容量的那个割
2. 求解最大流问题
2.1 枚举算法
时间复杂度： O(2^|V|·|E|)
思路：枚举所有割(S,T)，找到容量c(S,T)最小的那个割的容量，即为最大流的流值
评价：算法复杂度高，因此仅当顶点个数|V|较少时适用（否则整数越界）；另外，它还不能给出得到最大流的具体的网络流，只是返回了最大流值。
//source在最低位，对应1；sink在最高位，对应0。
//sink * * * * * * source
// 0 0 0 0 0 0 0 1
// 0 0 0 0 0 0 1 1
// 0 . . . . . . 1 ==>每一种二进制组合对应一个割
// 0 1 1 1 1 1 1 1
// | |
// ------ i -------
//用int i枚举二进制组合
int maxflow(){
int flow=INF;
int tmp;
for(int i=0;i<(1<<n-2);i++){
//枚举每一个割(S,T). S中元素对应位为1, T中元素对应为为0
s=(i<<1)|1;
tmp=0;
for(int u=0;u<n;u++)
for(int v=0;v<n;v++)
if( ((s>>u)&1)==1 && ((s>>v)&1)==0 )
tmp+=c[u][v];
if(flow>tmp) flow=tmp;
}
return flow;
}
2.2 增广路算法
FORD-FULKERSON方法：
f=0 while( p exists) do f+=p
其中，f是流值|f|不断增加的网络流，初始时f=0，之后不断沿着增广路径压入正网络流；
p是每次找到的增广路径。
FORD-FULKERSON抽象算法：（抽象两个字是我加上去的，因为这里并没有指定寻找增广路径的具体算法）
FORD-FULKERSON(G,s,t)
for each edge(u,v)∈E[G]
do f[u,v] <- 0
f[v,u] <- 0
while there exists a path p from s to t in the residual network Gf
do cf(p) <- min{cf(u,v): (u,v) is in p}
for each edge(u,v) in p
do f[u,v] <- f[u,v] + cf(p) //“沿着”增广路径，有向边上的流“增加”增广路径残留容量cf(p)
f[v,u] <- - f[u,v] //“逆着”增广路径，有向边上的流“减少”增广路径残留容量cf(p)
tips：
BFS时间复杂度=O(|E|);
DFS时间复杂度=O(|E|);
A. DFS搜索增广路径
时间复杂度：O(|E|·c), c是最大流 ==>每次搜索增广路径需要O(|E|)；可以增广O(c)次，∵每次可以增广大小为1的流
思路：每次DFS得到一条盲目的增广路径增广
评价：经证明，若每次从最短增广路径开始增广，则最多只用进行O(|V||E|)次增广，而不是DFS搜索增广路径的O(c)次。从这个意义上讲，DFS搜索增广路径是盲目的。
B. BFS搜索增广路径 （即“Edmonds-Karp算法”）
时间复杂度：O(|V|·|E|^2) ==>每次搜索增广路径需要O(|E|)；可以增广O(|V||E|)次，原因见下面评价
思路：每次BFS得到一条最短的增广路径增广
评价：经证明(independently proved by Dinic in 1970, and by Edmonds & Karp in 1972)，若每次从最短增广路径开始增广，则最多只用进行O(|V||E|)次增广，而不是DFS搜索增广路径的O(c)次。其中“最短增广路径”指的是：当每条边长度都为1时的最短路径，显然，最朴素的想法就是用BFS来找这种最短路径。
C. SAP (shortest augmenting path)
时间复杂度：O(|V|^2·|E|) ==>每次搜索增广路径需要O(|V|)；可以增广O(|V||E|)次，原因见下面评价
思路：每次"沿着从源到汇的允许弧（必然是源到汇的最短路径）"得到一条最短的增广路径增广。
允许弧：如果一条弧(u,v)满足h[u]=h[v]+1 ，即前点仅比后点高1
评价：经证明(independently proved by Dinic in 1970, and byEdmonds & Karp in 1972)，若每次从最短增广路径开始增广，则最多只用进行O(|V||E|)次增广，而不是DFS搜索增广路径的O(c)次。本质类似"BFS搜索增广路径"，只不过找最短路径的方法不同。再次注意，其中“最短增广路径”指的是：当每条边长度都为1时的最短路径
D. Dinic
时间复杂度：
思路：
评价：
2.3 预流推进算法（即《算法导论》26.4 压入和重标记算法）
Drainage Ditches ==> http://poj.org/problem?id=1273
DFS搜索增广路径：
#include <cstdio>
#include <cstring>
#define N 201
int n; //有向边数
int m; //顶点数
int f[N][N]; //网络流
int cf[N][N]; //残留网络
bool vis[N]; //DFS中是否访问过
const int inf = 1<<29;
int inline min(int x,int y){return x>y?y:x;}
bool dfs(int s,int t,int &cf_path)
{
vis[s]=true;
if(s==t)
return true;
for(int i=1;i<=m;++i)
{
if(vis[i]==false && cf[s][i]>0)
{
int temp = cf_path;
cf_path=min(cf_path,cf[s][i]); //(a)式
if(dfs(i,t,cf_path))
{
f[s][i]+=cf_path;
cf[s][i]-=cf_path;
cf[i][s]+=cf_path; //允许“反悔”
return true;
}
//沿着<s,i>向下深搜失败，回溯时恢复增广路径的残留容量cf[path];
//实际上是在撤销(a)式的影响!
cf_path = temp;
}
}
return false;
}
int find(int s=1,int t=m) //这实际上是DFS的外围框架（回忆DFS算法实现有内外两层）
{
int cf_path = inf; //本次可增广的流量，在DFS过程中被限制得越来越小
memset(vis,0,sizeof(vis));
dfs(s,t,cf_path);
if(cf_path>=inf)
return 0;
else
return cf_path;
}
int max_flow()
{
int ret=0,i;
memset(f,0,sizeof(f));
while(find());
for(i=1;i<=m;++i)
ret+=f[1][i]; //网络流的值=从源出发的流量和f(s,V)=流入汇点的流量和f(V,t)
return ret;
}
int main(void)
{
int i,x,y,z;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(cf,0,sizeof(cf));
for(i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
cf[x][y]+=z;
}
printf("%d\n",max_flow());
}
return 0;
}
BFS搜索增广路径——Edmonds-karp算法：
#include<iostream>
#include<queue>
using namespace std;
const int N=210;//边
const int INF=0x7FFFFFFF;
int n,m;
int map[N][N]; //残留图，初始状态标识每条有向边的容量的图也可以看做是一个残留图
int pi[N]; //BFS的前驱图; pi[start]=0；pi[i]=-1，如果i没有在BFS中被扩展过
int flow_in[N]; //流入i的最大流量是flow_in[i]
int start,end;
queue<int> q;
int bfs(){
int i,t;
while(!q.empty()) q.pop();
memset(pi,-1,sizeof(pi));
pi[start]=0;
flow_in[start]=INF; //key!
q.push(start);
while(!q.empty()){
t=q.front();
q.pop();
if(t==end) break;
for(i=1;i<=m;i++){
if(pi[i]==-1 && map[t][i]){
flow_in[i]=flow_in[t]<map[t][i]?flow_in[t]:map[t][i];
q.push(i);
pi[i]=t;
}
}
}
if(pi[end]==-1) return -1; //不存在增广路径
else return flow_in[m]; //还存在增光路径，不保证flow_in[m]达到最大可能值
}
int Edmonds_Karp(){
int max_flow_in=0; //流f的流值|f|
int cf_p; //增广路径的残留容量Cf(p)
int now,pre;
while((cf_p=bfs())!=-1){
//1. 流值|f|增加本次增广路径的残留容量cf_p
max_flow_in+=cf_p;
//2. 顺着和逆着增广路径压入网络流
now=end;
while(now!=start){
pre=pi[now];
map[pre][now]-=cf_p; //更新正向边的实际容量
map[now][pre]+=cf_p; //添加反向边
now=pre;
}
}
return max_flow_in;
}
int main(){
int i,u,v,cost;
while(scanf("%d%d",&n,&m)!=EOF){
memset(map,0,sizeof(map));//对于int[]/int[][]，memset只能正常赋予0,-1两个值
for(i=0;i<n;i++){
scanf("%d%d%d",&u,&v,&cost);
map[u][v]+=cost;
}
start=1,end=m;
printf("%d\n",Edmonds_Karp());
}
return 0;
}
SAP算法：
/*
测试用例：
6 5
1 2 2
1 3 5
2 4 1
3 4 6
3 5 1
4 5 5
*/
#include<stdio.h>
#include<string.h>
#define INF 1<<29;
struct sap
{
int s,t; //s:源点 t:汇点
int m; //顶点数
int cf[305][305]; //残留容量
int flow; //当前最大流
int cf_path; //本次可增广的流量（本次增广路径的残留容量）
bool flag; //本次增广路径是否找到
int vh[1000]; //各高度的顶点个数
int h[1000]; //各顶点的高度，又称为“距离标号”——到汇点距离的下界（边权值都为1）
sap(){
flow =cf_path =s =t =0;
flag=false;
memset(cf,0,sizeof(cf));
memset(vh,0,sizeof(vh));
memset(h,0,sizeof(h));
}
/*find_path_sap(int cur):增广路径已经推进到顶点cur，尝试向下一个顶点推进
主要思路：
递归地尝试沿着当前点cur的所有允许弧推进增广路径。
如果失败，将当前点cur的高度（距离函数下界）更新到minH(minH:残留网络中所有cur指向节点的最小高度)
*/
void find_path_sap(int cur){
//1. 检查是否走到增广路径末端
//*a. 终止条件：cur是本次增广路径末端节点(汇点)
if(cur==t){
flow+=cf_path;
flag=true;
return;
}
//2. 尝试递归/回溯 找增广路径
//如果cur仅比邻接点高1，则尝试最大限度向它送出流
int i;
int minH=m-1;
int tmp_cf_path=cf_path;
for(i=1;i<=m;i++){
if(cf[cur][i]){
if(h[i]+1==h[cur]){
if(cf[cur][i]<cf_path)
cf_path=cf[cur][i];
find_path_sap(i);
//*b. 终止条件: 如果h[1]增长到m，表示通过本次"find_path_sap(i)"递归搜索，不能找到一条增广路径
if(h[1]>=m)
return;
//*c. 终止条件: 通过本次"find_path_sap(i)"递归搜索，找到了一条增广路径
if(flag)
break;
//通过本次"find_path_sap(i)"递归没有找到一条增广路径，回溯时需要恢复状态
cf_path=tmp_cf_path;
}
if(h[i]<minH)
minH=h[i];
}
}
//以上for()执行完，minH为cur的邻接顶点中高度最小的点的高度
//3. 检查回溯结果
// 成功：逆着增广路径压入增广的流
// 失败：顶点cur高度增加1
if(flag){
//上面代码中的某次递归成功找到一条增广路径(从cur找下去，找到一条增广路径)
cf[cur][i]-=cf_path;
cf[i][cur]+=cf_path;
}else{
vh[h[cur]]--;
if(vh[h[cur]]==0)
h[1]=m; //作用到终止条件"*b"
h[cur]=minH+1;
vh[h[cur]]++;
}
}
//Ford-Fulkerson算法框架
int solve(){
vh[0]=m;
flow=0;
//h[1]保持<m，一旦增长到m，就不再存在任何增广路径
while(h[1]<m)
{
flag=false;
cf_path=INF;
find_path_sap(s);
}
return flow;
}
void addEdge(int x,int y,int c){
cf[x][y]+=c;
}
};
int main(){
int n; //有向边数
int m; //顶点数
while(scanf("%d %d",&n,&m)!=-1)
{
sap nt= sap();
nt.s=1;
nt.t=m;
nt.m=m;
for(int i=1;i<=n;i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
nt.addEdge(x,y,c);
}
printf("%d\n",nt.solve());
}
return 0;
}