记录编号	606445	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 方格取数问题	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	0.088 s
提交时间	2025-09-25 20:49:39	内存使用	8.80 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct flowGraph
{
    struct edge {
      int v, nxt, cap, flow;
    } edges[222225];
    int head[222225], cnt = 0;
    int n, s, t;
    int maxflow = 0;
    int dist[222225], cur[222225];
    void init(int _n, int _s, int _t) {
        memset(head, -1, sizeof(head));
        cnt = 0;
        s = _s;
        t = _t;
        n = _n;
    }
    void addedge(int u, int v, int w) {
        edges[cnt] = {v, head[u], w, 0};
        head[u] = cnt++;
        edges[cnt] = {u, head[v], 0, 0};
        head[v] = cnt++;
    }
    bool bfs() {
        queue<int> q;
        memset(dist, 0, sizeof(int) * (n + 1));
        dist[s] = 1;
        q.push(s);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edges[i].nxt) {
                int v = edges[i].v;
                if ((!dist[v]) && (edges[i].cap > edges[i].flow)) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        return dist[t];
    }
    int dfs(int u, int flow) {
        if ((u == t) || (!flow)) {
            return flow;
        }
        int ret = 0;
        for (int &i = cur[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].v, f;
            if ((dist[v] == dist[u] + 1) && (f = dfs(v, min(flow - ret, edges[i].cap - edges[i].flow)))) {
                ret += f;
                edges[i].flow += f;
                edges[i ^ 1].flow -= f;
                if (ret == flow) {
                    return ret;
                }
            }
        }
        return ret;
    }
    int dinic() {
        while (bfs()) {
            memcpy(cur, head, sizeof(int) * (n + 1));
            maxflow += dfs(s, 0x3f3f3f3f3f3f);
        }
        return maxflow;
    }
} g;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int calc(int x, int y)
{
    return x * 100 + y;
}
signed main()
{
    freopen("grid.in", "r", stdin);
    freopen("grid.out", "w", stdout);
    int n, m; 
    cin >> n >> m;
    g.init(222222, 0, 111111);
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            cnt += a[i][j];
            if ((i + j) % 2) {
                g.addedge(0, calc(i, j), a[i][j]);
                for (int k = 0; k < 4; k++) {
                    int dx = i + dir[k][0];
                    int dy = j + dir[k][1];
                    if (1 <= dx && dx <= n && 1 <= dy && dy <= m) {
                        g.addedge(calc(i, j), calc(dx, dy), 0x3f3f3f3f);
                    }
                }
            } else {
                g.addedge(calc(i, j), 111111, a[i][j]);
            }
        }
    }
    cout << cnt - g.dinic();
    return 0;
}