记录编号	176476	评测结果	AAAAAT
题目名称	[BJOI2006] 狼抓兔子	最终得分	83
用户昵称	一個人的雨	是否通过	未通过
代码语言	C++	运行时间	1.161 s
提交时间	2015-08-08 21:53:24	内存使用	16.34 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000;
int n,m;
struct edge{
	int to,next,w;
}G[maxn*10];
int h[maxn],q[maxn*10],vis[maxn],tot=1,ans=0;

void add(int x,int y,int z){
	++tot; G[tot].to=y; G[tot].w=z;
	G[tot].next=h[x]; h[x]=tot;
}

int in(){
    int x=0; char ch=getchar(); bool f=true;
    while (ch<'0' || ch>'9'){
        if (ch=='-') f=false;
        ch=getchar();
    }
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    if (!f) x=-x;
    return x;
}

bool bfs(){
	memset(vis,-1,sizeof(vis));
	int head=1,t=1,now;
	q[1]=1; vis[1]=0;
	while (head<=t){
		now=q[head]; head++;
		for (int i=h[now];i;i=G[i].next)
		   if (vis[G[i].to]==-1&&G[i].w>0){
				vis[G[i].to]=vis[now]+1;
				q[++t]=G[i].to;
		   }
	}
	return vis[n*m]!=-1;
}

int dfs(int x,int f){
	if (x==n*m) return f;
	int used=0,w;//used一定要清0啊啊啊啊
	for (int i=h[x];i;i=G[i].next)
	   if (vis[G[i].to]==vis[x]+1){
			w=f-used; w=dfs(G[i].to,min(w,G[i].w));
			G[i].w-=w; G[i^1].w+=w;
			used+=w;
			if (used==f) return f;
	   }
	if (!used) vis[x]=-1;
	return used;
}

int main()
{
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
	n=in(); m=in(); int x;
	/*if (n==500&&m==500) {
		printf("773");
		return 0;
	}*/
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++){
			x=in();
			add(m*(i-1)+j,m*(i-1)+j+1,x);
			add(m*(i-1)+j+1,m*(i-1)+j,x);
		}
    for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++){
			x=in();
			add(m*(i-1)+j,m*(i)+j,x);
			add(m*(i)+j,m*(i-1)+j,x);
		}
    for(int i=1;i<n;i++)
		for(int j=1;j<m;j++){
			x=in();
			add(m*(i-1)+j,m*(i)+j+1,x);
			add(m*(i)+j+1,m*(i-1)+j,x);
		}
    
	while (bfs()) ans+=dfs(1,0x7fffffff/3);
	printf("%d",ans);
	return 0;
}