记录编号	98503	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	隨風巽	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2014-04-23 15:09:19	内存使用	0.51 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 200000000
using namespace std;
struct Edge{int from,to,cap,flow;};
const int MAXN=10000+10;
struct Dinic
{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>g[MAXN];
	queue<int>q;
	bool visited[MAXN];
	int d[MAXN],cur[MAXN];
	void INITIALIZE(int n)
	{
		this->n=n;
		for(int i=0;i<=n;i++)g[i].clear();
		edges.clear();
	}
	void ADD(int from,int to,int cap)
	{
		edges.push_back((Edge){from,to,cap,0});
		edges.push_back((Edge){to,from,cap,0});
		m=edges.size();
		g[from].push_back(m-2);
		g[to].push_back(m-1);
	}
	bool BFS(void)
	{
		int v,i;
		memset(visited,0,sizeof(visited));
		q.push(s);
		d[s]=0;visited[s]=true;
		while(!q.empty())
		{
			v=q.front();q.pop();
			for(i=0;i<g[v].size();i++)
			{
				Edge &e=edges[g[v][i]];
				if(not visited[e.to]&&e.cap>e.flow)
				{
					d[e.to]=d[v]+1;
					q.push(e.to);
					visited[e.to]=true;
				}
			}
		}
		return visited[t];
	}
	int DFS(int v,int a)
	{
		if(v==t||a==0)return a;
		int flow=0,f;
		for(int& i=cur[v];i<g[v].size();i++)
		{
			Edge& e=edges[g[v][i]];
			if(d[v]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
			{
				e.flow+=f;
				edges[g[v][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a==0)break;
			}
		}
		return flow;
	}
	int MAXFLOW(int s,int t)
	{
		int flow=0;
		this->s=s;this->t=t;
		while(BFS())
		{
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
		}
		return flow;
	}
};
Dinic NF;
int T,N,M,F;
int ID(int i,int j){return (i-1)*M+j;}
int main()
{
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	int i,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&N,&M);
		NF.INITIALIZE(ID(N,M));
		for(i=1;i<=N;i++)
			for(j=1;j<=M-1;j++)
			{
				scanf("%d",&F);
				NF.ADD(ID(i,j),ID(i,j+1),F);
			}
		for(i=1;i<=N-1;i++)
			for(j=1;j<=M;j++)
			{
				scanf("%d",&F);
				NF.ADD(ID(i,j),ID(i+1,j),F);
			}
		cout<<NF.MAXFLOW(ID(1,1),ID(N,M))<<endl;
	}
	return 0;
}