标签：

「JSOI2015」圈地

传送门

显然是最小割。

首先对付所有屋子，，权值 \(> 0\) 的连边 \(s \to i\) ，权值 \(< 0\) 的连边 \(i \to t\) ，然后对付所有的墙，连两条边，连接起墙两边的屋子，容量就是修墙的用度，然后直接用权值和 - 最小割就是最大收益。

参考代码：

#include <cstring> #include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) template < class T > inline T min(T a, T b) { return a < b ? a : b; } template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 400 * 400 + 5, __ = 3 * 400 * 400 + 5, INF = 2147483647; int tot = 1, head[_]; struct Edge { int v, w, nxt; } edge[__ << 1]; inline void Add_edge(int u, int v, int w) { edge[++tot] = (Edge) { v, w, head[u] }, head[u] = tot; } inline void link(int u, int v, int w) { Add_edge(u, v, w), Add_edge(v, u, 0); } int n, m, x, sum, s, t, dep[_], cur[_]; inline int bfs() { static int hd, tl, Q[_]; memset(dep, 0, sizeof (int) * (t - s + 1)); hd = tl = 0, Q[++tl] = s, dep[s] = 1; while (hd < tl) { int u = Q[++hd]; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].v, w = edge[i].w; if (dep[v] == 0 && w) dep[v] = dep[u] + 1, Q[++tl] = v; } } return dep[t] > 0; } inline int dfs(int u, int flow) { if (u == t) return flow; for (rg int& i = cur[u]; i; i = edge[i].nxt) { int v = edge[i].v, w = edge[i].w; if (dep[v] == dep[u] + 1 && w) { int res = dfs(v, min(w, flow)); if (res) { edge[i].w -= res, edge[i ^ 1].w += res; return res; } } } return 0; } inline int Dinic() { int res = 0; while (bfs()) { for (rg int i = s; i <= t; ++i) cur[i] = head[i]; while (int d = dfs(s, INF)) res += d; } return res; } inline int id(int i, int j) { return (i - 1) * m + j; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), read(m), s = 0, t = n * m + 1; for (rg int i = 1; i <= n; ++i) for (rg int j = 1; j <= m; ++j) { read(x), sum += x > 0 ? x : -x; if (x > 0) link(s, id(i, j), x); if (x < 0) link(id(i, j), t, -x); } for (rg int i = 1; i <= n - 1; ++i) for (rg int j = 1; j <= m; ++j) read(x), link(id(i, j), id(i + 1, j), x), link(id(i + 1, j), id(i, j), x); for (rg int i = 1; i <= n; ++i) for (rg int j = 1; j <= m - 1; ++j) read(x), link(id(i, j), id(i, j + 1), x), link(id(i, j + 1), id(i, j), x); printf("%d\n", sum - Dinic()); return 0; }

「JSOI2015」圈地