记录编号	501823	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2018-07-23 18:51:37	内存使用	69.18 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define id(x,y) (((x)-1)*m+(y))
using namespace std;
const int maxn=10010,maxe=3000010;
struct edge{int to,cap,prev;}e[maxe<<1];
void AddEdge(int,int,int);
int ISAP();
void bfs();
int augment();
int last[maxn],cnte=0,d[maxn],p[maxn],c[maxn],cur[maxn],q[maxn];
int T,n,m,s,t,tmp;
int main(){
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		memset(last,-1,sizeof(last));
		cnte=0;
		scanf("%d%d",&n,&m);
		s=1;t=n*m;
		for(int i=1;i<=n;i++)for(int j=1;j<m;j++){
			scanf("%d",&tmp);
			if(tmp){
				AddEdge(id(i,j),id(i,j+1),tmp);
				AddEdge(id(i,j+1),id(i,j),tmp);
			}
		}
		for(int i=1;i<n;i++)for(int j=1;j<=m;j++){
			scanf("%d",&tmp);
			if(tmp){
				AddEdge(id(i,j),id(i+1,j),tmp);
				AddEdge(id(i+1,j),id(i,j),tmp);
			}
		}
		printf("%d\n",ISAP());
	}
	return 0;
}
void AddEdge(int x,int y,int z){
	e[cnte].to=y;
	e[cnte].cap=z;
	e[cnte].prev=last[x];
	last[x]=cnte++;
}
int ISAP(){
	bfs();
	memcpy(cur,last,sizeof(cur));
	int x=s,flow=0;
	while(d[s]<t){
		if(x==t){
			flow+=augment();
			x=s;
		}
		bool ok=false;
		for(int &i=cur[x];~i;i=e[i].prev)
			if(e[i].cap&&d[x]==d[e[i].to]+1){
				p[e[i].to]=i;
				x=e[i].to;
				ok=true;
				break;
			}
		if(!ok){
			int tmp=t-1;
			for(int i=last[x];~i;i=e[i].prev)
				if(e[i].cap)tmp=min(tmp,d[e[i].to]+1);
			if(!--c[d[x]])break;
			c[d[x]=tmp]++;
			cur[x]=last[x];
			if(x!=s)x=e[p[x]^1].to;
		}
	}
	return flow;
}
void bfs(){
	memset(d,-1,sizeof(d));
	memset(c,0,sizeof(c));
	int head=0,tail=0;
	d[t]=0;
	q[tail++]=t;
	while(head!=tail){
		int x=q[head++];
		c[d[x]]++;
		for(int i=last[x];~i;i=e[i].prev)
			if(e[i^1].cap&&d[e[i].to]==-1){
				d[e[i].to]=d[x]+1;
				q[tail++]=e[i].to;
			}
	}
}
int augment(){
	int a=(~0u)>>1;
	for(int x=t;x!=s;x=e[p[x]^1].to)a=min(a,e[p[x]].cap);
	for(int x=t;x!=s;x=e[p[x]^1].to){
		e[p[x]].cap-=a;
		e[p[x]^1].cap+=a;
	}
	return a;
}