网络流24题 方格取数问题

题目传送门

好久没做网络流了……

---

对棋盘进行黑白染色，黑色点连源点，白色点连汇点
因为相邻的点不能同时选，所以要在相邻的点间连容量为(inf)的边
然后用所有方格的价值和减去最小割即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 21474836
using namespace std;
int read() {
    int k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        k = k * 10 + c - 48, c = getchar();
    }
    return k * f;
}
struct zzz {
    int t, len, nex;
}e[100010 << 1]; int head[10010], tot = 1;
void add(int x, int y, int z) {
    e[++tot].t = y;
    e[tot].len = z;
    e[tot].nex = head[x];
    head[x] = tot;

    e[++tot].t = x;
    e[tot].len = 0;
    e[tot].nex = head[y];
    head[y] = tot;
}
int s = 1, t = 2, vis[10010];
bool bfs() {
    queue <int> q; q.push(s);
    memset(vis, 0, sizeof(vis)); vis[s] = 1;
    while(!q.empty()) {
        int k = q.front(); q.pop();
        for(int i = head[k]; i; i = e[i].nex) {
            if(!vis[e[i].t] && e[i].len) {
                vis[e[i].t] = vis[k] + 1; q.push(e[i].t);
                if(e[i].t == t) return 1;
            }
        }
    }
    return vis[t];
}
int dfs(int flow, int pos) {
    if(!flow || pos == t) return flow;
    int fl, rest = 0;
    for(int i = head[pos]; i; i = e[i].nex) {
        if(vis[e[i].t] == vis[pos] + 1 && (fl = dfs(min(e[i].len, flow-rest), e[i].t))) {
            e[i].len -= fl, e[i^1].len += fl, rest += fl;
            if(rest == flow) return rest;
        }
    }
    if(rest < flow) vis[pos] = 0;
    return rest;

}
int dinic() {
    int ans = 0;
    while(bfs()) {
        ans += dfs(1 << 30, s);
        //cout << ans << endl;
    }
    return ans;
}
int map[110][110], n, m, sum;
int fx[5] = {0, 1, -1, 0, 0},
    fy[5] = {0, 0, 0, 1, -1};
inline int id(int x, int y) {
    return (x - 1) * m + y + 2;
}
int main() {
   n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            map[i][j] = read(), sum += map[i][j];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if((i+j) & 1) add(s, id(i, j), map[i][j]);
            else add(id(i, j), t, map[i][j]);
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if((i+j) & 1) {
                for(int k = 1; k <= 4; ++k) {
                    int xx = i + fx[k], yy = j + fy[k];
                    if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
                    add(id(i,j), id(xx, yy), INF);
                }
            }
        }
    cout << sum - dinic();

    return 0;
}

双倍经验：Luogu P4474 王者之剑