记录编号	605009	评测结果	AAAAAA
题目名称	752.[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	0.817 s
提交时间	2025-08-13 12:59:36	内存使用	8.30 MiB

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N=1e6+10,M=6e6+10,inf=1e9+10;
int n,m,s,t,mincut,ver[N],to[M],nxt[M],val[M],d[N],now[N],idx=1;
queue<int>q;
int id(int x,int y){
	return x*m-m+y;
} 
void add(int x,int y,int z){
	to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z;
	to[++idx]=x,nxt[idx]=ver[y],ver[y]=idx,val[idx]=z;
}
bool bfs(){
	while(q.size())q.pop();
	for(int i=s;i<=t;i++)d[i]=0,now[i]=ver[i];
	d[s]=1,q.push(s);
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=ver[x];i;i=nxt[i]){
			if(val[i]&&!d[to[i]]){
				d[to[i]]=d[x]+1,q.push(to[i]);
				if(to[i]==t)return 1; 
			}
		}
	} 
	return 0;
}
int dinic(int x,int flow){
	if(x==t||!flow)return flow;
	int used=0,f;
	for(int i=now[x];i;i=nxt[i]){
		now[x]=i;
		if(val[i]&&d[to[i]]==d[x]+1){
			f=dinic(to[i],min(val[i],flow-used));
			if(!f)d[to[i]]=0;
			else val[i]-=f,val[i^1]+=f,used+=f;
			if(used==flow)break;
		}
	}
	return used;
}
signed main(){
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m-1;j++){
			int x;cin>>x;
			add(id(i,j),id(i,j+1),x);
		}
	}
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=m;j++){
			int x;cin>>x;
			add(id(i,j),id(i+1,j),x);
		}
	}
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=m-1;j++){
			int x;cin>>x;
			add(id(i,j),id(i+1,j+1),x);
		}
	}
	s=id(1,1),t=id(n,m); 
	while(bfs())mincut+=dinic(s,inf);
	printf("%lld\n",mincut);
	return 0;
}