最小割
套路最小割。。。
盗一波图 来自GXZ神犇
对于这样的图，我们要么割ai,bj,要么割bi,aj,要么割ai,ci+cj,aj,要么割bi,ci+cj,bj,然后这样建图跑最小割就行了
但这不是重点，这道题我t了大概一个月，不知道为什么，怎么和别人比对代码好像没有什么差异，结果发现判断delta=0不能放在for循环里，否则会很慢。。。俞勇的红书不靠谱啊。。。怪不得我的网络流那么慢。。。
#include<bits/stdc++.h> using namespace std; const int N = 10010, inf = 1000000010; const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; int head[N], d[N], q[N], iter[N]; struct edge { int nxt, to, f; } e[N * 50]; int n, cnt = 1, source, sink, ans, m; #define id(i, j) (i - 1) * m + j int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } void link(int u, int v, int f) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; e[cnt].f = f; } void insert(int u, int v, int f) { link(u, v, f); link(v, u, 0); } bool bfs() { queue<int> q; q.push(source); memset(d, 0, sizeof(d)); d[source] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; i; i = e[i].nxt) if(e[i].f && !d[e[i].to]) { d[e[i].to] = d[u] + 1; q.push(e[i].to); if(e[i].to == sink) return true; } } return false; } int dfs(int u, int delta) { if(u == sink || delta == 0) return delta; int ret = 0; for(int &i = iter[u]; i; i = e[i].nxt) if(e[i].f && d[e[i].to] == d[u] + 1) { int x = dfs(e[i].to, min(e[i].f, delta)); if(x == 0) d[e[i].to] = 0; e[i].f -= x; e[i ^ 1].f += x; delta -= x; ret += x; if(delta == 0) return ret; } return ret; } int dinic() { int ret = 0; while(bfs()) { for(int i = source; i <= sink; ++i) iter[i] = head[i]; ret += dfs(source, inf); } return ret; } int main() { scanf("%d%d", &n, &m); sink = n * m + 1; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) { int x, a = id(i, j); scanf("%d", &x); ans += x; if((i + j) & 1) insert(source, a, x); else insert(a, sink, x); } for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) { int x, a = id(i, j); scanf("%d", &x); ans += x; if((i + j) & 1) insert(a, sink, x); else insert(source, a, x); } for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) { int x, a = id(i, j), b; scanf("%d", &x); for(int k = 0; k < 4; ++k) { int xx = i + dx[k], yy = j + dy[k]; b = id(xx, yy); if(xx > 0 && xx <= n && yy > 0 && yy <= m) { ans += x; insert(a, b, x); insert(b, a, x); } } } printf("%d ", ans - dinic()); return 0; }