记录编号	337456	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-11-04 15:45:26	内存使用	0.54 MiB

#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),ch>'9'||ch<'0')if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x*f;
}
#define maxe 20010
#define maxn 210
struct edge
{
	int t,n,f;
}a[maxe];
int len=-1,head[maxn],dis[maxn],n;
bool vis[maxn];
void insert(int x,int y,int z)
{
	a[++len].t=y;a[len].f=z;a[len].n=head[x];head[x]=len;
}
int min(int x,int y){return x<y?x:y;}
#define k a[i].t
#define inf 0x7f7f7f7f
void bfs()
{
	memset(dis,0,sizeof dis);
	vis[1]=1;
	std::queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i>-1;i=a[i].n)
			if(a[i].f&&!vis[k])
			{
				vis[k]=1;dis[k]=dis[x]+1;
				q.push(k);
			}
	}
}
int dfs(int x,int flow)
{
	if(x==n)return flow;
	int ret=0;
	for(int i=head[x];flow&&i>-1;i=a[i].n)
		if(a[i].f&&dis[k]==dis[x]+1)
		{
			int d=dfs(k,min(flow,a[i].f));
			a[i].f-=d;
			a[i^1].f+=d;
			ret+=d;
			flow-=d;
		}
	return ret;
}
int main()
{
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
    n=read();
    memset(head,-1,sizeof head);
    for(int i=1,x;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
			x=read();
			if(!x)continue;
			insert(i,j,x);
			insert(j,i,0);
		}
	int ret=0;
	while(1)
	{
		memset(vis,0,sizeof vis);
		bfs();
		if(!vis[n])break;
		ret+=dfs(1,inf);
	}
	printf("%d",ret);
//	system("pause");
	fclose(stdin);
	fclose(stdout);
}