记录编号	605432	评测结果	AAAAAA
题目名称	752.[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	1.281 s
提交时间	2025-09-01 10:51:49	内存使用	43.55 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,M=2000006;
const int inf=1000000007;
int n,m,s,t,tot=2,hd[M],a[N][N],cnt;
struct node{
	int to,nxt;
	int val;
}e[M];
void add(int u,int v,int w){
	e[tot].to=v;
	e[tot].val=w;
	e[tot].nxt=hd[u];
	hd[u]=tot;
	tot++;
	e[tot].to=u;
	e[tot].val=w;
	e[tot].nxt=hd[v];
	hd[v]=tot;
	tot++;
}
int cur[M],d[M];
bool bfs(){
	memset(d,0,sizeof(d));
	queue<int> q;
	q.push(1);
	d[1]=1;
	while(!q.empty()){
		int f=q.front();
		q.pop();
		for(int i=hd[f];i;i=e[i].nxt){
			int v=e[i].to;
			if(d[v]==0&&e[i].val>0){
				d[v]=d[f]+1;
				q.push(v);
				if(v==cnt) return true;
			}
		}	
	}
	return false;
}
int dfs(int u,int mf){
	if(u==cnt) return mf;
	int sum=0;
	for(int i=cur[u];i&&mf;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].to;
		if(d[v]==d[u]+1&&e[i].val){
			int f=dfs(v,min(mf,e[i].val));
			if(f==0) d[v]=0;
			e[i].val-=f;
			e[i^1].val+=f;
			sum+=f;
			mf-=f;
			if(mf==0) break;
		}
	}
	if(sum==0) d[u]=0;
	return sum;
}
void Dinic(){
	int flow=0;
	while(bfs()){
		memcpy(cur,hd,sizeof(hd));
		flow+=dfs(1,inf);
	}
	cout<<flow;
	return;
}
signed main(){
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cnt++;
			a[i][j]=cnt;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			int k;
			cin>>k;
			add(a[i][j],a[i][j+1],k);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			int k;
			cin>>k;
			add(a[i][j],a[i+1][j],k);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			int k;
			cin>>k;
			add(a[i][j],a[i+1][j+1],k);
		}
	}
	Dinic();
	return 0;
}