记录编号	172888	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2015-07-27 15:19:21	内存使用	58.09 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 30000
using namespace std;
typedef long long ll;
int n,m,S=0,T;
ll a[110][110],b[110][110];
const ll inf=((ll)1<<60)-1;
struct Edge{
	int to,next;
	ll dis;
}edge[maxn*100];
int h[maxn],cnt;
void add(int u,int v,ll d){
	cnt++;
	edge[cnt].to=v;
	edge[cnt].next=h[u];
	edge[cnt].dis=d;
	h[u]=cnt;
}
ll dis[maxn];
int q[maxn*100];
bool vis[maxn];
ll SPFA(){
	memset(vis,0,sizeof vis);
	for(int i=S;i<=T;i++)dis[i]=inf;
	int head=0,tail=1;
	dis[S]=0;q[head]=S;vis[S]=1;
	while(head!=tail){
		int u=q[head];
		for(int i=h[u];i;i=edge[i].next){
			int v=edge[i].to;
			if(dis[u]+edge[i].dis<dis[v]){
                dis[v]=dis[u]+edge[i].dis;
				if(!vis[v])vis[v]=1,q[tail++]=v;
			}
		}
		vis[u]=0,head++;
	}
	return dis[T];
}
int main(){
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	int test;
	scanf("%d",&test);
	while(test--){
		scanf("%d%d",&n,&m);
		if(n==1||m==1){
			ll x=inf;
            for(int i=1;i<=n;i++)
				for(int j=1;j<m;j++){
                    scanf("%lld",&a[i][j]);
					x=min(x,a[i][j]);
				}

			for(int i=1;i<n;i++)
		    	for(int j=1;j<=m;j++){
                    scanf("%lld",&b[i][j]);
                    x=min(x,b[i][j]);
		    	}

			printf("%lld\n",x);
			continue;
		}
		cnt=0;T=(n-1)*(m-1)+1;
		memset(h,0,sizeof h);
		for(int i=1;i<=n;i++)
			for(int j=1;j<m;j++)
				scanf("%lld",&a[i][j]);
		for(int i=1;i<n;i++)
		    for(int j=1;j<=m;j++)
		        scanf("%lld",&b[i][j]);

		for(int i=1;i<m;i++){
			add(S,i,a[1][i]);add(i,S,a[1][i]);
		}
		for(int i=1;i<n;i++){
			add(S,i*(m-1),b[i][m]);add(i*(m-1),S,b[i][m]);
		}
		for(int i=1;i<m;i++){
			add((n-2)*(m-1)+i,T,a[n][i]);
			add(T,(n-2)*(m-1)+i,a[n][i]);
		}
		for(int i=1;i<n;i++){
		    add((i-1)*(m-1)+1,T,b[i][1]);
		    add(T,(i-1)*(m-1)+1,b[i][1]);
		}
		for(int i=1;i<n;i++)
			for(int j=1;j<m;j++){
				int x=(i-1)*(m-1)+j;
				if(j!=m-1){add(x,x+1,b[i][j+1]);add(x+1,x,b[i][j+1]);}
				if(i!=n-1){add(x,x+m-1,a[i+1][j]);add(x+m-1,x,a[i+1][j]);}
			}
		printf("%lld\n",SPFA());
	}
	return 0;
}