记录编号	605042	评测结果	AAAAAA
题目名称	752.[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.805 s
提交时间	2025-08-13 14:56:42	内存使用	15.46 MiB

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define val(i, j) ((i - 1) * m + j)

const int MAXN = 1005, MAXM = 6e6 + 10;
int h[MAXN * MAXN], cnt[MAXN * MAXN], d[MAXN * MAXN], tot = 1;
int n, m, S, T, ans;

struct node{
    int to, next, w;
}e[MAXM];

void add(int u, int v, int w){
    e[++ tot] = {v, h[u], w};
	h[u] = tot;
    e[++ tot] = {u, h[v], w};
	h[v] = tot;
}

bool bfs(){
    memset(d, 0, sizeof d);
    queue<int> q;
    q.push(S); d[S] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = h[u];i;i = e[i].next){
            int v = e[i].to;
            if(!d[v] && e[i].w){
                d[v] = d[u] + 1;
                if(v == T) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int u, int flow){
    if(u == T) return flow;
    int res = 0;
    for(int i = cnt[u];i;i = e[i].next){
        int v = e[i].to;
        if((d[v] == d[u] + 1) && e[i].w){
            int k = dfs(v, min(flow - res, e[i].w));
            if(!k) d[v] = 0;
            e[i].w -= k;
            e[i ^ 1].w += k;
            res += k;
            if(res == flow) break;
        }
    }
    return res;
}

int main(){
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m;
    S = val(1,1), T = val(n,m);
    for(int i = 1, w;i <= n;i ++){
    	for(int j = 1;j < m;j ++){
            cin >> w;
            int u = val(i, j), v = val(i, j + 1);
            add(u, v, w);
        }
	}
    for(int i = 1, w;i < n;i ++){
    	for(int j = 1;j <= m;j ++){
            cin >> w;
            int u = val(i, j), v = val(i + 1, j);
            add(u, v, w);
        }
	}
    for(int i = 1, w;i < n;i ++){
    	for(int j = 1;j < m;j ++){
            cin >> w;
            int u = val(i, j), v = val(i + 1,j + 1);
            add(u, v, w);
        }
	}
    while(bfs()){
        memcpy(cnt, h, sizeof h);
        ans += dfs(S, 1e9);
    }
    cout << ans << '\n';
    return 0;
}