poj 1273 Drainage Ditches

题目大意：对于一个排水系统，求它的最大排水速度。

即最大流，用的是标号增广路算法。

#include <stdio.h>
#include <string.h>
#include <math.h>
#define INF 100000000
int min(int a,int b)
{
	if(a>b)
		return b;
	else
		return a;
}
struct node
{
	int c,f;
}map[210][210];

int m,n,flag[210],prev[210],alpha[210];
int queue[300];
int qs,qe,v;
void ford()
{
	int i;
	while(1)
	{
		memset(flag,-1,sizeof(flag));
		memset(alpha,-1,sizeof(alpha));
		memset(prev,-1,sizeof(prev));
		flag[1]=0;prev[1]=1;alpha[1]=INF;
		qs=0;qe=1;
		queue[0]=1;
		while(qs<qe&&flag[n]==-1)
		{
			v=queue[qs]; qs++;
			for(i=1;i<=n;i++)
			{
				if(flag[i]==-1)
				{
					if(map[v][i].c<INF&&map[v][i].f<map[v][i].c)
					{
						flag[i]=0;
						prev[i]=v;
						alpha[i]=min(alpha[v],map[v][i].c-map[v][i].f);
						queue[qe++]=i;
					}
					else if(map[i][v].c<INF&&map[i][v].f>0)
					{
						flag[i]=0;
						prev[i]=-v;
						alpha[i]=min(alpha[v],map[i][v].f);
						queue[qe++]=i;
					}
				}
			}
			flag[v]=1;
		}
		if(flag[n]==-1||alpha[n]==0)
			break;
		int k1=n,k2=abs(prev[k1]);
		int a=alpha[n];
		while(1)
		{
			if(map[k2][k1].f<INF)
				map[k2][k1].f+=a;
			else map[k1][k2].f-=a;
			if(k2==1)
				break;
			k1=k2;
			k2=abs(prev[k2]);
		}
	}
	int max=0;
	for(i=2;i<=n;i++)
	{
		if(map[1][i].c<INF)
			max+=map[1][i].f;
		if(map[i][1].c<INF)
			max-=map[i][1].f;

	}
	printf("%d
",max);
}

int main()
{
	int i,j;
	int x,y,w;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				map[i][j].c=INF;
				map[i][j].f=0;
			}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&x,&y,&w);
			if(map[x][y].c<INF)
				map[x][y].c+=w;
			else
				map[x][y].c=w;
		}
		ford();
	}
	return 0;
}