记录编号	258395	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	粘粘自喜	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-05-05 19:54:51	内存使用	34.77 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define T 2001
using namespace std;
inline int read() {
	int x=0; char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
	return x;
}
int m,n,head[2005],q[2005],dis[2005],from[2005],a[2005],b[2005],cnt,ans;
int c[2005][2005];
bool inq[2005];
struct data{int from,to,next,v,c;}e[1000001];

void ins(int u,int v,int w,int c)
{
    cnt++;
    e[cnt].from=u;e[cnt].to=v;
    e[cnt].v=w;e[cnt].c=c;
    e[cnt].next=head[u];head[u]=cnt;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
void build(int k)
{
     cnt=1;memset(head,0,sizeof(head)); 
     for(int i=1;i<=m;i++)insert(0,i,a[i],0);
     for(int i=1;i<=n;i++)insert(m+i,T,b[i],0);
     for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
           insert(i,m+j,inf,k*c[i][j]);
     }
inline bool spfa()
{
    for(int i=0;i<=T;i++)dis[i]=inf;
    int t=0,w=1,i,now;
    dis[0]=q[0]=0;inq[0]=1;
    while(t!=w)
    {
        now=q[t];t++;if(t==200)t=0;
        for(int i=head[now];i;i=e[i].next)
        {
            if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c)
            {
                from[e[i].to]=i;
                dis[e[i].to]=dis[now]+e[i].c;
                if(!inq[e[i].to])
                {
                    inq[e[i].to]=1;
                    q[w++]=e[i].to;
                    if(w==200)w=0;
                }
            }
        }
        inq[now]=0;
    }
    if(dis[T]==inf)return 0;return 1;
}
inline void end()
{
    int i,x=inf;
    i=from[T];
    while(i)
    {
        x=min(e[i].v,x);
        i=from[e[i].from];
    }
    i=from[T];
    while(i)
    {
        e[i].v-=x;
        e[i^1].v+=x;
        ans+=x*e[i].c;
        i=from[e[i].from];
    }
}
int main()
{
	freopen("tran.in","r",stdin);
	freopen("tran.out","w",stdout);
    m=read();n=read();
    for(int i=1;i<=m;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=m;i++)
       for(int j=1;j<=n;j++)
          c[i][j]=read();
    build(1);
    while(spfa())end();
    printf("%d\n",ans);ans=0;
    build(-1); 
    while(spfa())end();
    printf("%d\n",-ans);
    return 0;
}