记录编号	467469	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	_小妖	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2017-10-30 17:27:51	内存使用	0.47 MiB

#include<iostream>
#include<cstdio> 
#include<queue>
#include<cstring>
using namespace std;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')f=0;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return f?x:-x;
}
const int inf=2147483646;
int n;
int tmp;
int ans;
struct node{
	int flow,to,last;
}tu[10000];
int head[210],tot=1;
void add(int x,int y,int v)
{
	tot++;
	tu[tot].to=y,tu[tot].last=head[x];
	head[x]=tot;
	tu[tot].flow=v;
}
int use[210];
int q[10000];
int h,t;
bool vis[210];
int c[210];
bool bfs()
{
//	memset(vis,0,sizeof(vis));
	memset(c,0,sizeof(c));
	c[1]=1;
//	q.push(1);
	h=1,t=0;
	q[++t]=1;
	while(h<=t)
	{
		int k=q[h];
		h++;
		for(int i=head[k];i;i=tu[i].last)
		{
			int to=tu[i].to;
			if(!c[to]&&tu[i].flow)
			{
				c[to]=c[k]+1;
				q[++t]=to;
			}
		}
	}
	return c[n];
}
int m_flow(int now,int want)
{
	if(now==n||want==0)return want;
	int f=0,to,flow;
	for(int i=head[now];i;i=tu[i].last)
	{
		to=tu[i].to;
		if(c[to]==c[now]+1&&tu[i].flow)
		{
			flow=m_flow(to,min(want,tu[i].flow));
			if(!flow)continue;
			f+=flow,want-=flow;
//			use[now]=i;
			tu[i].flow-=flow,tu[i^1].flow+=flow;
			if(!want)break;
		}
	}
	return f;
}
int main()
{
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			tmp=read();
			if(tmp)
			{
				add(i,j,tmp),add(j,i,0);
			}
		}
	}
	int ta;
	while(bfs())
	{
//		for(int i=1;i<=n;++i)use[i]=head[i];
		while(ta=m_flow(1,inf))ans+=ta;
	}
	printf("%d",ans);
	return 0;
}