PART 1 什么是网络流
网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。【引自百度百科】
PART 2 一些概念
容量网络:设G(V,E),是一个有向网络,在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);对于每一条弧<u,v>属于E,对应有一个权值c(u,v)>0,称为弧的容量.通常吧这样的有向网络G称为容量网络.
弧的流量:通过容量网络G中每条弧<u,v>,上的实际流量(简称流量),记为f(u,v);
最大流:在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.
增广路:
设f是一个容量网络G中的一个可行流,P是从Vs到Vt 的一条链,若P满足以下条件:
a.P中所有前向弧都是非饱和弧,
b.P中所有后向弧都是非零弧.
则称P为关于可行流f 的一条增广路.
沿这增广路改进可行流的操作称为增广.
残留容量:给定容量网络G(V,E),及可行流f,弧<u,v>上的残留容量记为cl(u,v)=c(u,v)-f(u,v).每条弧上的残留容量表示这条弧上可以增加的流量.因为从顶点u到顶点v的流量减少,等效与从顶点v到顶点u的流量增加,所以每条弧<u,v>上还有一个反方向的残留容量cl(v,u)=-f(u,v).
残留网络:设有容量网络G(V,E)及其上的网络流f,G关于f的残留网络记为G(V',E').其中G'的顶点集V'和G中顶点集G相同,V'=V.对于G中任何一条弧<u,v>,如果f(u,v)<c(u,v),那么在G'中有一条弧<u,v>属于E',其容量为c'(u,v)=c(u,v)-f(u,v),如果f(u,v)>0,则在G'中有一条弧<v,u>属于E',其容量为c'(v,u)=f(u,v).残留网络也称为剩余网络。
PART 3 Dinic算法的基本思路:
1.根据残量网络计算层次图。
2.在层次图中使用DFS进行增广直到不存在增广路
3.重复以上步骤直到无法增广
PART 4 代码简介
1.用链式前向星存储图
2.用bfs将图分层
3.用dfs进行增广
PART 5 模板（洛谷p3376）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf=1e9+7;
struct edge{
int c,to,next;
}e[210000];
int head[11000],cnt,level[11000];
void add(int u,int v,int w){
e[cnt].to=v;
e[cnt].c=w;
e[cnt].next=head[u];
head[u]=cnt++;
}
int bfs(int s,int t){
memset(level,-1,sizeof(level));
queue<int>q;
q.push(s);
level[s]=0;
while(!q.empty()){
int u;
u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(level[v]==-1&&e[i].c){
level[v]=level[u]+1;
q.push(v);
}
}
}
if(level[t]==-1)return 0;
return 1;
}
int dfs(int u,int v,int flow){
if(u==v)return flow;
int res=0;
for(int i=head[u];~i;i=e[i].next){
int j=e[i].to;
if(level[j]==level[u]+1&&e[i].c){
int f=dfs(j,v,min(flow-res,e[i].c));
res+=f;
e[i].c-=f;
e[i^1].c+=f;
}
}
if(!res)level[u]=-1;
return res;
}
int main()
{ int n,m,i,j,k,u,w,v,s,t,ans=0;
cin>>n>>m>>s>>t;
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
while(bfs(s,t))
while(int a=dfs(s,t,inf))
ans+=a;
cout<<ans<<endl;
return 0;
}
参考资料 http://blog.csdn.net/x_y_q_/article/details/51999466
百度百科