题目链接：http://poj.org/problem?id=1273
a.EK算法：(Edmond-Karp): 用BFS不断找增广路径，当找不到增广路径时当前流量即为最大流。
b.dinic算法：不断找最短路。
题意：现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量.
//http://blog.csdn.net/huzhengnan/article/details/7766446一个写的特别好的博客，包括好几种求最大流的写法；
EK(Edmonds_Karp):不断找增广路径，当找不到增广路径时当前流量即为最大流。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0xfffffff int F[][],C[][];
int a[],p[];
int n,m,sum; void EK()
{
queue<int>q;//BFS找增广路
while()
{
memset(a,,sizeof(a));
q.push();//原点入队
a[]=INF;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=; v<=m; v++)
{
if(!a[v] && C[u][v]-F[u][v]>)
{
p[v]=u;
q.push(v);
a[v]=min(a[u],C[u][v]-F[u][v]);
}
}
}
if(a[m]==)
break; /找不到增广路，则当前流即为最大流
sum+=a[m];
for(int i=m; i!=; i=p[i])
{
F[p[i]][i]+=a[m];
F[i][p[i]]-=a[m];
}
}
printf("%d\n",sum);
} int main()
{
int x,y,z;
while(scanf("%d%d",&n,&m)==)
{
memset(F,,sizeof(F));
memset(C,,sizeof(C));
memset(p,-,sizeof(p));
sum=;//记录最大流
while(n--)
{
scanf("%d%d%d",&x,&y,&z);
C[x][y]+=z;//可能会有相同边
}
EK();
}
return ;
}
flow[u][v]为<u,v>流量,cap[u][v]为<u,v>容量
a[i]表示源点s到节点i路径上的最小残留量、p[i]记录i的前驱。
反向弧的作用：
意义：前的流到a的流量，来退掉一些以往流到a的流量，是这些被退掉的流量能够通过别的路径到达汇点。
//俗话说，就是原来走3，现在走1我不在你那走了，我在你那少走点吗，能在别人那走更多。起到退回的作用，非常好理解！
空间优化的EK：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0xfffffff int C[][];
int a[],p[];
int n,m,sum; void EK()
{
queue<int>q;
while()
{
memset(a,,sizeof(a));
a[]=INF;
q.push();
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=; v<=m; v++)
{
if(!a[v] && C[u][v]>)
{
p[v]=u;
q.push(v);
a[v]=min(a[u],C[u][v]);
}
}
}
if(a[m]==) break;
sum+=a[m];
for(int i=m; i!=; i=p[i])
{
C[p[i]][i]-=a[m];
C[i][p[i]]+=a[m];
}
}
printf("%d\n",sum);
} int main()
{
int x,y,z;
while(scanf("%d%d",&n,&m)==)
{
sum=;
memset(C,,sizeof(C));
memset(p,-,sizeof(p));
while(n--)
{
scanf("%d%d%d",&x,&y,&z);
C[x][y]+=z;
}
EK();
}
return ;
} //省掉了一个flow数组。
dinic： https://comzyh.com/blog/archives/568/#Dinic-Code
邻接矩阵实现：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0xfffffff int C[][];
int dis[];
int q[],h,r;
int n,m,sum; int BFS()
{
memset(dis,-,sizeof(dis));
dis[]=;
h=;
r=;
q[]=;
while(h<r)
{
int j=q[++h];
for(int i=; i<=m; i++)
{
if(dis[i]< && C[j][i]>) //如果没有被访问过 并且两点之间“联通”
{
dis[i]=dis[j]+;//那么到原点的距离就加一
q[++r]=i;//队列中的第几个元素是谁
}
}
}
if(dis[m]>) return ; //如果可以找到原点到汇点的通路 那么即找到增广路 返回1
else return ; //汇点的DIS小于零,表明BFS不到汇点
} //Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广
int Find(int x,int low) //找到最小的流量
{
int a=;
if(x==m) return low; //如果当前点是汇点，返回当前增加的流量
for(int i=; i<=m; i++)
if(C[x][i]> && dis[i]==dis[x]+ && (a=Find(i,min(low,C[x][i])) ) )
{
//联通 是分成图的下一层 能到汇点
C[x][i]-=a;
C[i][x]+=a;
return a;
}
return ;
} int main()
{
int x,y,z,ans;
while(scanf("%d%d",&n,&m)==)
{
memset(C,,sizeof(C));
while(n--)
{
scanf("%d%d%d",&x,&y,&z);
C[x][y]+=z;
}
sum=;
while(BFS())//成功建立分图
while(ans=Find(,INF))//成功找到增广路经
sum+=ans;
printf("%d\n",sum);
}
return ;
}
dinic邻接表实现：
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; #define MAXN 210
#define INF 0xfffffff struct Edge
{
int st, ed;
int c;
int next;
} edge[MAXN << ]; int n, m;
int s, t;
int ans;
int e = ;
int head[MAXN];
int d[MAXN]; void init()
{
int i,j;
int a,b,c;
s=;
t=m;
e=;
ans=;
memset(head,- sizeof(head));
for(i=; i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[e].st=a;
edge[e].ed=b;
edge[e].c=c;
edge[e].next=head[a];
head[a]=e++;
edge[e].st=b;
edge[e].ed=a;
edge[e].next=head[b];
head[b]=e++;
}
} int bfs()
{
memset(d,-,sizeof(d));
queue<int> q;
d[s]=;
q.push(s);
int i;
int cur;
while(!q.empty())
{
cur=q.front();
q.pop();
for(i=head[cur]; i!=-; i=edge[i].next)
{
if(d[edge[i].ed]==- && edge[i].c > )
{
d[edge[i].ed]=d[cur] + ;
q.push(edge[i].ed);
}
}
}
if(d[t]<) return ;
return ;
} int dinic(int x, int flow)
{
if(x==t) return flow; int i,a;
for(i=head[x]; i!=-; i=edge[i].next)
{
if(d[edge[i].ed]==d[x]+ && edge[i].c> && (a=dinic(edge[i].ed, min(flow,edge[i].c))))
{
edge[i].c-=a;
edge[i^].c+=a;
return a;
}
}
return ;
} void solve()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
while(bfs())
{
int increment;
increment=dinic(, INF);
ans+=increment;
}
printf("%d\n",ans);
}
} int main()
{
#ifdef LOCAL
#endif
solve();
return ;
}
SAP有个优化就是 当出现断链时，就可以直接退出，还有个优化是当前弧的优化，这两个优化只需要一句话+一个数组就解决了，相当实惠，好的ISAP执行的效率真的非常高，这个写的ISAP用的是链式前向星法表示。 http://blog.csdn.net/shiqi_614/article/details/7982858（相关博客）
SPFA优化:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 500
#define MAXE 40000
#define INF 0x7fffffff
long ne,nv,tmp,s,t,index;
struct Edge
{
long next,pair;
long v,cap,flow;
} edge[MAXE];
long net[MAXN];
long ISAP()
{
long numb[MAXN],dist[MAXN],curedge[MAXN],pre[MAXN];
long cur_flow,max_flow,u,tmp,neck,i;
memset(dist,,sizeof(dist));
memset(numb,,sizeof(numb));
memset(pre,-,sizeof(pre));
for(i=; i<=nv ; i++)
curedge[i]=net[i];
numb[nv]=nv;
max_flow=;
u=s;
while(dist[s]<nv)
{
if(u==t)
{
cur_flow=INF;
for(i=s; i!=t; i=edge[curedge[i]].v)
{
if(cur_flow>edge[curedge[i]].cap)
{
neck=i;
cur_flow=edge[curedge[i]].cap;
}
}
for(i=s; i!=t; i=edge[curedge[i]].v)
{
tmp=curedge[i];
edge[tmp].cap-=cur_flow;
edge[tmp].flow+=cur_flow;
tmp=edge[tmp].pair;
edge[tmp].cap+=cur_flow;
edge[tmp].flow-=cur_flow;
}
max_flow+=cur_flow;
u=neck;
}
for(i=curedge[u]; i!=-; i=edge[i].next)
if(edge[i].cap> && dist[u]==dist[edge[i].v]+)
break;
if(i!=-)
{
curedge[u]=i;
pre[edge[i].v]=u;
u=edge[i].v;
}
else
{
if(==--numb[dist[u]]) break;
curedge[u]=net[u];
for(tmp=nv,i=net[u]; i!=-; i=edge[i].next)
if(edge[i].cap>)
tmp=tmp<dist[edge[i].v]?tmp:dist[edge[i].v];
dist[u]=tmp+;
++numb[dist[u]];
if(u!=s) u=pre[u];
}
} return max_flow;
}
int main()
{
long i,j,np,nc,m,n;
long a,b,val;
long g[MAXN][MAXN];
while(scanf("%d%d",&ne,&nv)!=EOF)
{
s=;
t=nv;
memset(g,,sizeof(g));
memset(net,-,sizeof(net));
for(i=; i<ne; i++)
{
scanf("%ld%ld%ld",&a,&b,&val);
g[a][b]+=val;
}
for(i=; i<=nv; ++i)
for(j=i; j<=nv; j++)
if(g[i][j]||g[j][i])
{
edge[index].next=net[i];
edge[index].v=j;
edge[index].cap=g[i][j];
edge[index].flow=;
edge[index].pair=index+;
net[i]=index++;
edge[index].next=net[j];
edge[index].v=i;
edge[index].cap=g[j][i];
edge[index].flow=;
edge[index].pair=index-;
net[j]=index++;
}
printf("%ld\n",ISAP());
}
return ;
}