挺簡單一個題，最小割模板
我的感覺就是可能建圖的時候會比較麻煩吧，畢竟三個方向。
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstring>
#include <iostream>#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;elsenum = 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 __NOTEPADPPstd::cin.get();std::cin.get();
#endifreturn 0;
}
