网络流改进SAP算法模版、HDU 1532 Drainage Ditches（解题报告）
转载请注明出处：http://write.blog.csdn.net/postlist
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1532
本次网络流算法看了两天了，先学习了EK算法，发现速度不够快，于是查找资料，得网络流诸多算法中主流算法（SAP算法）学习之。
相关链接：
1、网络流的算法分类：http://www.notonlysuccess.com/index.php/algorithm-of-network/
2、牛人博客，几种算法的分析：http://blog.csdn.net/abcjennifer/article/details/5556455
3、较详细的SAP算法分析：http://hi.baidu.com/hewei156/blog/item/f17038326b2f91c0a2cc2b78.html
今天看了挺久的HUD 3572 http://acm.hdu.edu.cn/showproblem.php?pid=1532 自己用下面的模版写，800多ms。 然后看了别人用邻接表存边时间在100以内! 遂学习之。
然后，然后重点来了！ 我发现这个模版竟然可以去掉宽搜那部分！！ 具体原因尚未确定。鉴于明天还要早起，先把代码贴在最后，明天再研究！
研究的一天多的代码模版（该模版正确性及可用性有待证明，以后若出现什么问题将进行修改）：
#include<iostream>#include<algorithm>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<queue>#include<math.h>#define maxn 205#define INF 100000000using namespace std;int n,m,s,t,ans;// n点数，m边数，s起点，t终点 int map[maxn][maxn],fa[maxn],gap[maxn],level[maxn];int fine_path(int u){ for(int i=1;i<=n;i++) if(map[u][i]>0 && level[u]==level[i]+1) return i; return -1;}int Advance(){ int i,minflow=INF; for(i=t;i!=s;i=fa[i]) if(minflow>map[fa[i]][i]) { minflow=map[fa[i]][i]; } for(i=t;i!=s;i=fa[i]) { map[fa[i]][i]-=minflow; map[i][fa[i]]+=minflow; } return minflow;}int retreat(int u){ int fine=INF; for(int i=1;i<=n;i++) if(map[u][i]>0 && fine>level[i]+1) fine=level[i]+1; if(fine==INF) fine=n; return fine;}int cxbsap(){ int i,j,v,u=s,flow=0; while(level[s]<=n) { v=fine_path(u); if(v>0) { fa[v]=u; u=v; if(u==t) { flow+=Advance(); u=s; } } else { if(--gap[level[u]]==0) return flow; v=retreat(u); gap[v]++; level[u]=v; if(u!=s) u=fa[u]; } } return flow;}int main(){// freopen("in.txt","r",stdin); int i,j,a,b,x; while(~scanf("%d%d",&m,&n)) {memset(map,0,sizeof(map)); memset(level,0,sizeof(level)); memset(gap,0,sizeof(gap)); for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&x); map[a][b]+=x; } s=1; t=n; ans=cxbsap(); printf("%d\n",ans); } return 0;}