学步园

const int null = -1;
const int VMAX = 500;
const int EMAX = 300000;

struct Edge
{
	int adj,next,re;    //指向的点，下一边的下标，逆边的下标
	int r;          //余留网边的容量
}h[EMAX+10];  //用下标模拟指针构邻接表
int p[VMAX+10],c;
int n,m,s,t;
int gap[VMAX+10],pre[VMAX+10],dis[VMAX+10];

//插边，k,l为端点，cap为边容量
void insert(int k,int l,int cap)
{
	h[++c].adj=l;
	h[c].r=cap;
	h[c].next=p[k];
	p[k]=c;
	h[c].re=c+1;   

    //逆边
	h[++c].adj=k;
	h[c].r=0;
	h[c].next=p[l];
	p[l]=c;
	h[c].re=c-1;    //与上面对应

}
int sap(int N)  //N为点数（包括源汇）
{
	memset(dis,0,sizeof(dis));
	memset(gap,0,sizeof(gap));
	gap[0]=N;
	int u=s,ca=inf,ans=0;
	while (dis[s]<N)
	{
		while (1)
		{
			bool flag=false;
			for (int j=p[u];j!=null;j=h[j].next)
			{
				int i=h[j].adj;
				if (h[j].r && dis[u]==dis[i]+1)
				{
					ca=min(ca,h[j].r);
					pre[i]=j;u=i;  //注意邻接表版的pre表示的是边
					if (i==t)
					{
						ans+=ca;
						while (i!=s)
						{
							u=pre[i];
							h[u].r-=ca;
							h[h[u].re].r+=ca;
							i=h[h[u].re].adj;
						}
						u=s;ca=inf;
					}
					flag=true;
					break;
				}
			}
			if (!flag) break;
		}

		int Min=N;
		for (int j=p[u];j!=null;j=h[j].next)
			if (h[j].r && dis[h[j].adj]<Min)
				Min=dis[h[j].adj];
		if (--gap[dis[u]] == 0) break;
		gap[dis[u]=Min+1]++;
		if (u!=s) u=h[h[pre[u]].re].adj;
	}
	
	return ans;
}


void init()
{
	c=-1;
	memset(p,-1,sizeof(p));
}

实例poj 1273
#include<stdio.h>
#include<string.h>
#define data 1<<29
#define min(a,b) ((a)>(b)?(b):(a))
const int null=-1;
const int maxe=41000;
const int maxv=210;
struct edge
{
	int adj,next,contain,re;
}edges[maxe];
int p[maxv],c,start,endp,gap[maxv],pre[maxv],dis[maxv];
void insert(int point1,int point2,int cap)
{
	edges[++c].adj=point2;
	edges[c].contain=cap;
	edges[c].next=p[point1];
	p[point1]=c;
	edges[c].re=c+1;

	edges[++c].adj=point1;
	edges[c].contain=0;
	edges[c].next=p[point2];
	p[point2]=c;
	edges[c].re=c-1; 

}
int sap(int N)
{
	memset(dis,0,sizeof(dis));
	memset(gap,0,sizeof(gap));
	gap[0]=N;
	int u=start,ca=data,ans=0;
	while (dis[start]<N)
	{
		while (1)
		{
			bool flag=false;
			for (int j=p[u];j!=null;j=edges[j].next)
			{
				int i=edges[j].adj;
				if (edges[j].contain && dis[u]==dis[i]+1)
				{
					ca=min(ca,edges[j].contain);
					pre[i]=j;
					u=i;  
					if (i==N)
					{
						ans+=ca;
						while (i!=start)
						{
							u=pre[i];
							edges[u].contain-=ca;
							edges[edges[u].re].contain+=ca;
							i=edges[edges[u].re].adj;
						}
						u=start;
						ca=data;
					}
					flag=true;
					break;
				}
				
			}
			if (!flag) break;
			
		}

		int Min=N;
		for (int j=p[u];j!=null;j=edges[j].next)
			if (edges[j].contain && dis[edges[j].adj]<Min)
				Min=dis[edges[j].adj];
		if (--gap[dis[u]] == 0) break;
		gap[dis[u]=Min+1]++;
		if (u!=start) u=edges[edges[pre[u]].re].adj;
	}
	return ans;
}
void init()
{
	c=-1;
	memset(p,-1,sizeof(p));
}
int main()
{
	int n,m,i,j,a,b,t;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		
		init();
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a,&b,&t);
			insert(a,b,t);
		}
		start=1;
		printf("%dn",sap(m));
	}
	return 0;
}