网络流改进SAP算法模版、HDU 1532 Drainage Ditches（解题报告）

本次网络流算法看了两天了，先学习了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

研究的一天多的代码模版（该模版正确性及可用性有待证明，以后若出现什么问题将进行修改）：
[cpp]
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#define maxn 205
#define INF 100000000
using namespace std;

int n,m,s,t;// n点数，m边数，s起点，t终点
int map[maxn][maxn],fa[maxn],gap[maxn],level[maxn];//map有向图，fa父节点，
//gap[i]=j表示以汇点距离为i的点有j个，level[i]=j表示点i与汇点距离为j

void sap_bfs()//反向 BFS 初始化所有顶点的距离标号、初始化level和gap数组
{
    memset(level,1,sizeof(level));//这个很神奇，每个int的4字节都变成0000 0001
//即数组被初始化为二进制的00000001 00000001 00000001 00000001 ，十进制为16843009
    memset(gap,0,sizeof(gap));
    queue<int> q;
    q.push(t);
    level[t]=0;//汇点距离为0
    gap[level[t]]++;
    while(!q.empty())
    {
        int temp=q.front(); q.pop();
        for(int i=1;i<=n;i++)
        if(level[i]>n && map[i][temp]>0)
        {
            q.push(i);
            level[i]=level[temp]+1;
            gap[level[i]]++;
        }
    }
}

int fine_path(int u)//查找残量网络中是否有与u相连且距离为1的点
{
    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)//对点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;//找不到的话设置为最大，即点u不会再被经过
    return fine;
}

int cxbsap()
{
    sap_bfs();
    int i,j,v,u=s,flow=0;//初始化
    while(level[s]<=n)//源点与汇点距离小于n时执行，要是不存在源点到汇点的通路直接跳出
    {
        v=fine_path(u);// 找u的下一个点
        if(v>0)
        {
            fa[v]=u;//找到后标记父节点
            u=v;//把v赋值给u，如果不是汇点，直接跳回75行了
            if(u==t)
            {
                flow+=Advance();
                u=s;//找的一条路径后重新查找
            }
        }
        else
        {
            if(--gap[level[u]]==0) return flow;//如果其中一个距离个数为0，即出现断层，没有通路看，直接跳出
            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));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&x);
            map[a][b]+=x;
        }
        s=1; t=n;
        int ans=cxbsap();
        printf("%d\n",ans);
    }
    return 0;
}

我发现其实自己有点易做图症，我喜欢带参数的函数，所以：
[cpp]
/*
网络流改进sap模版：HDU1532
计算一个点编号1~n的网络的最大流；
时间复杂度o(v*e^2) v点数，e边数
陈小宾，2012、8、13凌晨
*/
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#define maxn 205
#define INF 100000000
using namespace std;

int n,m;// n点数，m边数，s起点，t终点
int map

补充：软件开发 , C++ ,