记录编号	145253	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-01-04 07:00:29	内存使用	0.55 MiB

#include<iostream>
#include<cstdio>
using namespace std;
struct www{int to,w,ne;}a[20010];
int n,i,p,zj1,zj2,zj3,sj=1,ans=0;
int head[110]={0},cnt[110]={0},h[110]={0},pre[110]={0},pres[110]={0},cur[110]={0};
bool flag;
int que[150]={0},quehead=1,quetail=0;
int GET(){que[0]--;int x=que[quehead];if(++quehead==150)quehead=1;return x;}
void PUSH(int x){if(++quetail==150)quetail=1;que[quetail]=x,que[0]++;}

void init()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	for(p=1;p<=n;p++)
	{
		scanf("%d",&zj1);
		if(zj1)
		{
			a[++sj].to=p,a[sj].ne=head[i],head[i]=sj,a[sj].w=zj1;
			a[++sj].to=i,a[sj].ne=head[p],head[p]=sj,a[sj].w=0;
		}
	}
	PUSH(n);
	while(que[0])
	{
		zj1=GET();
		for(i=head[zj1];i;i=a[i].ne)
		if(!a[i].w&&!h[a[i].to])
		{
			h[a[i].to]=h[zj1]+1;
			cnt[h[a[i].to]]++;
			PUSH(a[i].to);
		}
	}
	cnt[h[n]]--,h[n]=0;
}

void sap()
{
	for(i=1;i<=n;i++)cur[i]=head[i];
	int U=1;pre[U]=U;zj2=1e8;cnt[0]=1;
	while(h[1]<n)
	{
		flag=0;
		for(i=cur[U];i;i=a[i].ne)
		{
			if(a[i].w>0&&h[a[i].to]==h[U]-1)
			{
				flag=1,pre[a[i].to]=U,U=a[i].to;
				if(a[i].w<zj2)zj2=a[i].w;
				if(U==n)
				{
					while(U!=1)U=pre[U],a[cur[U]].w-=zj2,a[cur[U]^1].w+=zj2;
					ans+=zj2,zj2=1e8;
				}
				break;
			}
			cur[U]=a[i].ne;
		}
		if(flag)continue;
		if(!(--cnt[h[U]]))break;
		zj3=n;
		for(i=head[U];i;i=a[i].ne)
		if(a[i].w>0&&zj3>h[a[i].to])zj3=h[a[i].to],cur[U]=i;
		h[U]=zj3+1,cnt[h[U]]++,U=pre[U];
	}
	printf("%d\n",ans);
}

int main()
{
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	init();
	sap();
	//while(1);
	return 0;
}