SAP

经实践证明，SAP在稠密图甚至比效率分析最快的HLPP还要快，而在稀疏图里也仅比HLPP慢20％，而代码量直逼单纯dfs增广，绝对是最为划算的网络流做法，附代码。

{
    允许弧:(u,v)满足d[u]+1=d[v]
    如果一条弧(u,v)不是允许弧，则它重新成为允许弧的必要条件事d[u]改变
}
program ditch_sap;
var
    g,c,f:array[0..1000,0..1000] of longint;        {残量网络}
    vd,d:array[0..1000] of longint;                 {d:标号距离, vd:数组vd[i]记录标号距离为i的顶点个数}
    m,n,x,y,z,flow,ans,i:longint;
function min(a,b:longint):longint;
begin
    min:=a; if a>b then min:=b;
end;
 
function dfs(u,flow:longint):longint;			
var
    v,tmp:longint;
begin
    if u=n then  exit(flow);     {找到增广路}
 
    dfs:=0;  		 {min_d:u在残量网络里相通的边的最小标号距离,初始不能变为maxint}
    for v:=1 to n do if (g[u,v]>0 ) and (d[u]=d[v]+1) then {如果是允许弧}
    begin
        tmp:=dfs(v,min(flow-dfs,g[u,v]));		 {如果找到，增广}
        dec(g[u,v],tmp);
        inc(g[v,u],tmp);
        if c[u,v]>0 then inc(f[u,v],tmp) else dec(f[v,u],tmp);  {记录好的流量}
        dfs:=dfs+tmp;
        if dfs=flow then exit(dfs);
    end;
    if d[1]>=n then exit;           {如果源点的标号距离大于n,即不存在增广路,这一步放在重标号之前}
    dec(vd[d[u]]);
    if vd[d[u]]=0 then d[1]:=n;     {如果该标号距离的顶点是唯一的,那么删除后图出现断层}
    d[u]:=d[u]+1;
    inc(vd[d[u]]);
end;
begin
    assign(input,'ditch.in'); reset(input);
	assign(output,'ditch.out'); rewrite(output);
	readln(m,n);
	for i:=1 to m do
	begin
	    read(x,y,z);
	    inc(g[x,y],z);
	    inc(c[x,y],z);
	end;
	vd[0]:=n;
	while d[1]<n do
	begin
	    flow:=dfs(1,maxlongint);
	    inc(ans,flow);
	end;
	writeln(ans);
	close(input); close(output);
end.

代码没有错，经多组强数据测试。

program maxflow_SAP_DFS;
var
  map:array[1..1000,1..1000] of longint;
  g:array[1..1000,0..1000] of longint;
  i,m,n,id,x,y,z,maxflow:longint;
  start,height,vheight:array[0..1000] of longint;
function min(x,y:longint):longint;begin if x<y then exit(x);exit(y);end;
function dfs(x,flow:longint):longint;
var
  i,j,k,minheight:longint;
begin
  if x=n then exit(flow);
  minheight:=n+1;
  for j:=1 to g[x,0] do
  begin
    i:=g[x,start[x]];
    if (map[x,i]>0) then
    begin
      if height[x]=height[i]+1 then
      begin
        k:=dfs(i,min(flow,map[x,i]));
        if height[1]>n then exit(0);
        if k>0 then
        begin
          dec(map[x,i],k);
          inc(map[i,x],k);
          exit(k);
        end;
        if height[1]>n then exit(0);
      end;
      minheight:=min(minheight,height[i]);
      if height[1]>n then exit(0);
    end;
    inc(start[x]);if start[x]>g[x,0] then start[x]:=1;
  end;
  dec(vheight[height[x]]);
  if vheight[height[x]]=0 then height[1]:=n+1;
  height[x]:=minheight+1;                                            //我是某位写sap的OIer，我的sap也是经过n多组强数据测试的，如果height[x]:=minheight＋１，
　　　　　　　　　　　　　　　　　　　　　　　　　　//对于类似二分图的图，第二层之间标号较小的点向标号较大的点连一些边，这个图用sap求会错，但是
　　　　　　　　　　　　　　　　　　　　　　　　　　//改成height[x]:=height[x]＋１又会对，不知是为什么，请写sap的注意。
                                              //回复：跟上面的对比一下，你没有 if dfs=flow then exit(dfs); 这句话
                                                      必须要有残量才能重标号
  inc(vheight[height[x]]);
  exit(0);
end;
begin
  assign(input,'ditch.in');reset(input);
  assign(output,'ditch.out');rewrite(output);
  readln(m,n);
  for i:=1 to n do start[i]:=1;
  for i:=1 to m do
  begin
    readln(x,y,z);
    if (map[x,y]=0) and (map[y,x]=0)then
    begin
      inc(g[x,0]);g[x,g[x,0]]:=y;
      inc(g[y,0]);g[y,g[y,0]]:=x;
    end;
    inc(map[x,y],z);
  end;
  maxflow:=0;
  fillchar(height,sizeof(height),0);
  fillchar(vheight,sizeof(vheight),0);
  while height[1]<=n do inc(maxflow,dfs(1,20000000));
  writeln(maxflow);
  close(input);close(output);
end.

// 去除流量、残量数组，直接在原图上操作
// 参考了第一份代码
/*
ID:t-x.h1
PROB:ditch
LANG:C++
*/
#include<cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
const int MAX=2100000000,MAXn=200+9;
int n,answer,g[MAXn][MAXn],d[MAXn],gap[MAXn],st=1,ed=n;
int sap(int u,int flow)
{
	if(u==ed)
		return flow;
	int res=flow,i,t;
	for(i=1;i<=n;++i)
		if(g[u][i] && d[u]==d[i]+1)
		{
			t=sap(i,min(res,g[u][i]));
			g[u][i]-=t,g[i][u]+=t;
			if(!(res-=t))
				return flow;
		}
	if(!--gap[d[u]])
		d[st]=n;
	++gap[++d[u]];
	return flow-res;
}
int main()
{
	int m,i,t1,t2,t3;
	freopen("ditch.in","r",stdin);freopen("ditch.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&t1,&t2,&t3);
		g[t1][t2]+=t3;
	}
	for(gap[0]=n;d[st]<n;)
		answer+=sap(st,MAX);
	printf("%d\n",answer);
	return 0;
}