挺简单一个题，最小割模板
我的感觉就是可能建图的时候会比较麻烦吧，毕竟三个方向。
#include#include #include #include #include #define debug(x) std::cout << #x << " = " << x << std::endl;#define __OPTIMIZED__INPUT__int nextInt(){ int num = 0; char c; bool flag = false; while ((c = std::getchar()) == ' ' || c == '\r' || c == '\n' || c == '\t'); if (c == '-') flag = true; else num = c - 48; while (std::isdigit(c = std::getchar())) num = num * 10 + c - 48; return (flag ? - 1 : 1) * num;}struct{ int to; int nex; int v;} e[600001];int head[600001];int h[600001], q[600001];int ans, n, m;void Insert(const int u, const int v, const int w){ static int tot = 0; tot++; e[tot].to = v; e[tot].v = w; e[tot].nex = head[u]; head[u] = tot;}bool bfs(){ int now, i; std::memset(h, 0xff, sizeof h); int t = 0; int w = 1; q[t] = 1; h[1] = 0; while (t < w) { now = q[t]; t++; i = head[now]; for (int i = head[now]; i; i = e[i].nex) if (e[i].v && h[e[i].to] < 0) { q[w++] = e[i].to; h[e[i].to] = h[now] + 1; } } if (h[n * m] == -1) return 0; return 1;}int dfs(const int x, const int f){ if (x == n * m) return f; int w, used = 0; for (int i = head[x]; i; i = e[i].nex) if (e[i].v && h[e[i].to] == h[x] + 1) { w = dfs(e[i].to, std::min(w, e[i].v)); e[i].v -= w; e[i + 1].v += w; used += w; if (used == f) return f; } if (!used) h[x] = -1;// debug(used); return used;}void Dinic(){ while (bfs()) ans += dfs(1, INT_MAX);}int main(int argc, char ** argv){ n = nextInt(); m = nextInt(); int x; for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) { x = nextInt(); Insert(m * (i - 1) + j, m * (i - 1) + j + 1, x); Insert(m * (i - 1) + j + 1, m * (i - 1) + j, x); } for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) { x = nextInt(); Insert(m * (i - 1) + j, m * i + j, x); Insert(m * i + j, m * (i - 1) + j, x); } for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) { x = nextInt(); Insert(m * (i - 1) + j, m * i + j + 1, x); Insert(m * i + j + 1, m * (i - 1) + j, x); } Dinic(); std::cout << ans/* << std::endl*/;#ifdef __NOTEPADPP std::cin.get(); std::cin.get();#endif return 0;}