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

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 200005;  // 节点数最大为 N*M + 2

struct Edge {
    int to, rev;
    int capacity;
    Edge(int to, int rev, int capacity) : to(to), rev(rev), capacity(capacity) {}
};

class Dinic {
public:
    vector<vector<Edge>> graph;
    vector<int> level;
    vector<int> ptr;

    Dinic(int n) {
        graph.resize(n);
        level.resize(n);
        ptr.resize(n);
    }

    void add_edge(int from, int to, int capacity) {
        graph[from].push_back(Edge(to, graph[to].size(), capacity));
        graph[to].push_back(Edge(from, graph[from].size() - 1, 0));
    }

    bool bfs(int s, int t) {
        queue<int> q;
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const auto& edge : graph[u]) {
                if (edge.capacity > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[u] + 1;
                    q.push(edge.to);
                    if (edge.to == t) return true;
                }
            }
        }
        return false;
    }

    int dfs(int u, int t, int flow) {
        if (u == t) return flow;
        while (ptr[u] < graph[u].size()) {
            Edge& edge = graph[u][ptr[u]];
            if (edge.capacity > 0 && level[edge.to] == level[u] + 1) {
                int min_flow = min(flow, edge.capacity);
                int result = dfs(edge.to, t, min_flow);
                if (result > 0) {
                    edge.capacity -= result;
                    graph[edge.to][edge.rev].capacity += result;
                    return result;
                }
            }
            ptr[u]++;
        }
        return 0;
    }

    int max_flow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (true) {
                int pushed = dfs(s, t, INF);
                if (pushed == 0) break;
                flow += pushed;
            }
        }
        return flow;
    }
};

int main() {
    freopen("bjrabbit.in","r",stdin);
    freopen("bjrabbit.out","w",stdout);
    int N, M;
    cin >> N >> M;

    int size = N * M + 2;
    Dinic dinic(size);

    auto node = [&](int i, int j) -> int { return (i - 1) * M + (j - 1) + 1; };

    int source = node(1, 1);
    int sink = node(N, M);

    // 读取横向道路的权值
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j < M; ++j) {
            int c;
            cin >> c;
            int u = node(i, j);
            int v = node(i, j + 1);
            dinic.add_edge(u, v, c);
            dinic.add_edge(v, u, c);
        }
    }

    // 读取纵向道路的权值
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j <= M; ++j) {
            int c;
            cin >> c;
            int u = node(i, j);
            int v = node(i + 1, j);
            dinic.add_edge(u, v, c);
            dinic.add_edge(v, u, c);
        }
    }

    // 读取斜向道路的权值
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < M; ++j) {
            int c;
            cin >> c;
            int u = node(i, j);
            int v = node(i + 1, j + 1);
            dinic.add_edge(u, v, c);
            dinic.add_edge(v, u, c);
        }
    }

    int max_flow = dinic.max_flow(source, sink);
    cout << max_flow << endl;

    return 0;
}