记录编号	237308	评测结果	AAAAAAAAAA
题目名称	运输问题2	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-03-16 19:54:01	内存使用	0.66 MiB

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
queue<int>q;
int S,T;
struct u
{
	int b;
	int z;
	int x;
}c[30000];
int d[110],h[110],l=-1,r[110];
inline void gj(int a,int b,int z)
{
	//if(z>0)
	//    printf("%d %d %d\n",a,b,z);
	c[++l].b=b;
	c[l].z=z;
	c[l].x=h[a];
	h[a]=l;
}
int n;
inline bool gb()
{
	memset(d,-1,sizeof(d));
	d[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
	//printf("gjx%d ",k);
		for(int i=h[k];i!=-1;i=c[i].x)
		if(c[i].z>0)
		{
			int u=c[i].b;
			if(d[u]==-1)
			{
				d[u]=d[k]+1;
				q.push(u);
			}
		}
	}
	if(d[T]==-1)
	    return 0;
	    //printf("sx");
	return 1;
}
inline int gd(int k,int s)
{
    if(k==T||s==0)
    {
        return s;
    }
    int used=0;
    for(int i=h[k];i!=-1;i=c[i].x)
    if(c[i].z>0)
    {
        int u=c[i].b;
        if(d[u]==d[k]+1)
        {
            int x=gd(u,min(s-used,c[i].z));
            if(x>0)
            {
                c[i].z-=x;
                c[i^1].z+=x;
                used+=x;
                if(used==s)
                    return used;
            }
            else
                d[u]=-1;
        }
    }
    return used;
}
int main()
{
	freopen("maxflowb.in","r",stdin);
	freopen("maxflowb.out","w",stdout);
	memset(h,-1,sizeof(h));
	scanf("%d",&n);
	S=n+1,T=n+2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int aa,bb;
			scanf("%d%d",&aa,&bb);
			if(bb==0)
			    continue;
			gj(i,j,bb-aa);
			gj(j,i,0);
			r[j]+=aa;
			r[i]-=aa;
		}
	}
	//printf("L%d\n",l);
	for(int i=1;i<=n;i++)
	{
		if(r[i]>0)
		{
			//printf("stone%d\n",S);
			gj(S,i,r[i]);
			gj(i,S,0);
		}
		else if(r[i]<0)
		{
			gj(i,T,-r[i]);
			gj(T,i,0);
		}
	}
	gj(n,1,0x3fffffff);
	gj(1,n,0);
	int w=0;
	//printf("USA%d   %d\n",l,h[S]);
	while(gb())
	    gd(S,0x3fffffff);
	//printf("%d\n",w);
	//getchar();
	//getchar();
	//return 0;
	c[l-1].z=0;
	S=1,T=n;
	while(gb())
	    w+=gd(S,0x3fffffff);
	printf("%d",w);
	getchar();
	getchar();
}