记录编号	159869	评测结果	AAAAAAAAAA
题目名称	运输问题2	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-04-22 21:09:52	内存使用	0.65 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 120
const int INF=1e9;
int du[N];
int n,m,i,p,zj1,zj2,zj3,ST,SD,ans,ANS;

int que[N],qhead=1,qtail=1;
inline void PUSH(int x){if(++qtail==N)qtail=1;que[0]++;que[qtail]=x;}
inline int GET(){int x=que[qhead];que[0]--;if(++qhead==N)qhead=1;return x;}

int to[N*N*2],ne[N*N*2],head[N],w[N*N*2],sj=1;
inline void addedge(int u,int v,int c)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=c;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=0;
}

void init()
{
	scanf("%d",&n);ST=n+1,SD=ST+1;
	for(i=1;i<=n;i++)for(p=1;p<=n;p++)
	{
		scanf("%d%d",&zj1,&zj2);
		if(!zj2)continue;
		du[i]-=zj1;du[p]+=zj1;
		addedge(i,p,zj2-zj1);
	}
	for(i=1;i<=n;i++)
	if(du[i]>0)addedge(ST,i,du[i]);
	else if(du[i]<0)addedge(i,SD,-du[i]);
	addedge(n,1,INF);
}
int pre[N],cnt[N],lv[N],cur[N];
void isap(int be,int en)
{
	ans=0;
	memset(cnt,0,sizeof(cnt));
	memset(lv,0,sizeof(lv));
	PUSH(en);while(que[0])
	for(zj1=GET(),i=head[zj1];i;i=ne[i])
	if(w[i^1]&&!lv[to[i]])
	cnt[lv[to[i]]=lv[zj1]+1]++,PUSH(to[i]);
	cnt[lv[en]]--,cnt[lv[en]=0]=SD;
	
	for(i=1;i<=SD;i++)cur[i]=head[i];
	bool flag;int U=be;pre[U]=U;zj1=INF;

	while(lv[be]<SD)
	{
		for(flag=0,i=cur[U];i;cur[U]=i=ne[i])
		if(w[i]&&lv[to[i]]==lv[U]-1)
		{
			flag=1;pre[to[i]]=U,U=to[i];
			if(zj1>w[i])zj1=w[i];
			if(U==en)
			{
				while(U!=be)U=pre[U],w[cur[U]]-=zj1,w[cur[U]^1]+=zj1;
				ans+=zj1,zj1=INF;
			}
			break;
		}
		if(flag)continue;
		if(!(--cnt[lv[U]]))break;
		for(zj2=SD,i=head[U];i;i=ne[i])
		if(w[i]&&zj2>lv[to[i]])zj2=lv[to[i]],cur[U]=i;
		cnt[lv[U]=zj2+1]++,U=pre[U];
	}
}
int main()
{
	freopen("maxflowb.in","r",stdin);
	freopen("maxflowb.out","w",stdout);
	init();
	isap(ST,SD);
	ANS+=w[head[1]];
	head[n]=ne[head[n]];
	head[1]=ne[head[1]];
	isap(1,n);
	ANS+=ans;
	printf("%d\n",ANS);
	return 0;
}