网络流基础入门，这里不说那些证明过程了，直接个人见解。
首先：最大流，顾名思义，是从源点出发，经过若干条路径，最后到达汇点的所有流的和。而这里最大流的确定条件是，当前的网络中不存在增广路了。那什么是增广路呢？就是当进行若干次操作后，当前网络还存在使最大流更大的路径，那么就是增广路了。如果当前网络不存在增广路的话，那么我们就无法再增加最大流了，那也就是最大流已经求解出来了。在求最大流的过程中，我们还要构建残余网络，还有一个反向流，据说是可以对之前的某些操作进行“反悔”，从而获得更大的流。
好了，下边是EK算法，书上也说是最短增广路算法，SAP算法。因为这里首先用了BFS算法。这个算法的作用是啥呢？就是从源点出发，运用队列，通过层次遍历，一直遍历到汇点。由于这个操作是基于BFS实现，那么求出的就是到汇点的最短路径。我们再来分析一遍。在BFS的过程中，我们还要更新每个点到下一个点可允许通过的最小流。因为一条增广路的最小流量肯定是这条路径上的最小容量，如果假设当前结点的流是F[CUR]，那么下一个点CUR+1可通过的流就是min(F[CUR]，Edge[CUR][CUR+1])，同时还要记住pre[CUR+1]=CUR，因为当我们找完所有路径到汇点的流之后，还要反过来更新每条边的容量，那么这里pre的作用就记录前驱了。当我们通过BFS找完当前网络所有到汇点的路径之后，假设汇点T的F[T]！=0，也就是还有到达汇点的流，并且这个到汇点的F[T]流肯定是某条增广路上的能够增加的流，然后我们就可以由汇点反推回来更新每条边的容量，当当前的可更新的流更新完之后，就接着就行BFS，继续找增广路，知道F[T]=0，此时就没有到达汇点的流，那么当前网络也就不存在增广路了。现在来分析一下EK的时间复杂度，在BFS的过程中，我们是从每个顶点开始BFS，那么当n个顶点，m条边的时候，此时的时间复杂度是O(n*m)，然后在更新流的过程中，我们也是通过路径即边来更新，所以EK算法时间复杂度为O(n*m*m); 注意这里的n是顶点数，m是边数（下边的代码刚好反过来）
下边贴上EK的算法模板，个人习惯写的，可以参考：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>
using namespace std;
int pre[250];
int n,m;
int edge[250][205];
int BFS(){
int value[205];
for(int i=1;i<=m;i++){
value[i]=0;
pre[i]=-1;
}
value[1]=0x3f3f3f3f;
pre[1]=-1;
queue<int> q;
q.push(1);
while(q.empty()==0){
int u=q.front();
q.pop();
for(int i=1;i<=m;i++){
if(edge[u][i]>0&&value[i]==0){
value[i]=min(edge[u][i],value[u]);
pre[i]=u;
q.push(i);
}
}
}
return value[m];
}
int EK(){
int ans=0;
int add;
while(add=BFS()){
ans+=add;
int u=m;
while(pre[u]!=-1){
int v=pre[u];
edge[u][v]+=add;
edge[v][u]-=add;
u=v;
}
}
return ans;
}
int main(){
//freopen("test.txt","r",stdin);
while(~scanf("%d%d",&n,&m)){
memset(edge,0,sizeof(edge));
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[u][v]+=w;
}
printf("%d\n",EK());
}
return 0;
}
OK，大概讲完EK，现在来讨论Dinic。Dinic又称连续最短增广路算法，这个算法是由BFS+DFS写成的。其实BFS的过程跟EK的过程差不多，只是这里不在BFS的过程中寻找流，而是做层次标记，从源点开始，不断做标记，这里也保持最短路的特性，如果当前点可以做标记的话，说明上一个点是通过某个大小的流到达当前点的，那么如果汇点可以做标记的话，说明是存在从源点到汇点的流，至于这个流的大小并不在BFS中求出。当做完BFS后，如果汇点可以被标记，那么我们就要从源点开始，做DFS操作，这个操作当让是基于最短路也是层次上实现的，下面来看看DFS的过程
int DFS(int s,int Max){
int ans=0;
if(s==m){
return Max;
}
for(int i=1;i<=m;i++){
if(edge[s][i]>0&&level[s]+1==level[i]){
int Min=min(Max-ans,edge[s][i]);
int f=DFS(i,Min);
edge[s][i]-=f;
edge[i][s]+=f;
ans+=f;
if(ans==Max){
return ans;
}
}
}
return ans;
}
s是当前点，Max是上一个点传到当前点的流，m是汇点。我们从for循环分析起。如果当前点可以到i点存在流，并且i点是s点的下一个层次的点（保持最短路的特性），那么我们就可以从i点继续DFS，好了，问题来了。这个 int Min=min(Max-ans,edge[s][i]); 有什么用呢？我们来分析下，Max是上一个点传下来的流量，ans是s这个层次除开i点外其他点使用完的流量，那么Max-ans当然就是可以供i点使用的流量了，,edge[s][i]当然就是流过i点的流量了，然后我们要取其中的最小值，继续传给下一个点，也就是继续DFS。那么DFS结束的条件当然就是遇到汇点了。如果s是汇点，Max是从上一个点到s点的流量，也就是最终流入汇点的流量了，那么本次DFS的过程也就结束了。然后就递归回去更新流，然后再DFS，知道该层次网络中没有增广路，那么就重新BFS规划层次网络，然后判断DFS。就没了。大家有没有发现Dinic和EK的一个区别，EK进行BFS，只能找一条增广路，Dinic进行一次BFS，存在找到多条增广路的可能性，这也就是说可以对该网络进行连续增广。那分析一下Dinic的时间复杂度，BFS花费的时间依旧是O(n*m)，在DFS的过程中，我们要进行层次遍历，那肯定是对于顶点进行层次标记，所以DFS的过程我们是对于顶点的遍历，那么DFS的时间是O(n)，所以整个Dinic的时间复杂度是O（n*n*m)
注意这里的n是顶点数，m是边数（下边的代码刚好反过来）
下边贴上EK的算法模板，个人习惯写的，可以参考：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>
using namespace std;
int pre[250];
int n,m;
int edge[250][205];
int level[250];
int BFS(){
memset(level,0,sizeof(level));
memset(pre,0,sizeof(pre));
queue<int> q;
q.push(1);
level[1]=1;
while(q.empty()==0){
int u=q.front();
q.pop();
for(int i=1;i<=m;i++){
if(edge[u][i]>0&&level[i]==0){
level[i]=level[u]+1;
q.push(i);
}
}
}
return level[m];
}
int DFS(int s,int Max){
int ans=0;
if(s==m){
return Max;
}
for(int i=1;i<=m;i++){
if(edge[s][i]>0&&level[s]+1==level[i]){
int Min=min(Max-ans,edge[s][i]);
int f=DFS(i,Min);
edge[s][i]-=f;
edge[i][s]+=f;
ans+=f;
if(ans==Max){
return ans;
}
}
}
return ans;
}
int Dinic(){
int ans=0;
while(BFS()){
ans+=DFS(1,0x3f3f3f3f);
}
return ans;
}
int main(){
//freopen("test.txt","r",stdin);
while(~scanf("%d%d",&n,&m)){
memset(edge,0,sizeof(edge));
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[u][v]+=w;
}
printf("%d\n",Dinic());
}
return 0;
}
经典最大流模板题： POJ - 1273 http://poj.org/problem?id=1273