BZOJ 1001
直接建图dinic，注意这题坑多
1 存边不要用vector，vector自动申请内存在不够的时候会申请多一倍，所以换数组或者reserve
2 原图是无向图，所以反向弧容量也是$c$而不是0
3 注意$n,m$和点就行
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 * 1000 + 5, MAXM = 3 * 1000 * 1000 + 5, INF = 2147483647;
struct data {int v, cap, flow;}ed[MAXM * 2];
//vector<data> ed;
vector<int> G[MAXN];
int n, m, s, t;
int getIDbyPos(int x, int y) {return y + (x - 1) * m;}
int en, cur[MAXN], d[MAXN], vis[MAXN];
void ins(int u, int v, int c) {
/*ed.push_back((data){v, c, 0}), G[u].push_back(en++);
ed.push_back((data){u, c, 0}), G[v].push_back(en++);*/
//vector存边会MLE，解决方案看下面
ed[en] = ((data){v, c, 0}), G[u].push_back(en++);
ed[en] = ((data){u, c, 0}), G[v].push_back(en++);
}
bool bfs() {
queue<int> q;
for (int i = 0; i <= n * m; i++) vis[i] = false;
d[s] = 0, vis[s] = true, q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
if (!vis[v] && cap > flow) {
vis[v] = true, d[v] = d[u] + 1, q.push(v);
}
}
}
return vis[t];
}
int dfs(int u, int a) {
if (u == t) return a;
if (a == 0) return 0;
int retflow = 0;
for (int &i = cur[u]; i < G[u].size(); i++) {
int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
if (cap > flow) {
if (d[v] == d[u] + 1) {
int f = dfs(v, min(a, cap - flow));
if (f > 0) {
a -= f, retflow += f, ed[G[u][i]].flow += f, ed[G[u][i] ^ 1].flow -= f;
if (a == 0) break;
}
}
}
}
return retflow;
}
int dinic() {
int flow = 0;
while (bfs()) {
for (int i = 0 ; i <= n * m; i++) cur[i] = 0;
flow += dfs(s, INF);
}
return flow;
}
void clean() {
//ed.reserve(MAXM); //vector申请空间太大，用这个调整就不会MLE
en = 0;
for (int i = 0; i <= n * m; i++) G[i].clear();
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
for (int x, j = 1; j <= m - 1; j++) {
scanf("%d", &x);
ins(getIDbyPos(i, j), getIDbyPos(i, j + 1), x);
}
}
for (int i = 1; i <= n - 1; i++) {
for (int x, j = 1; j <= m; j++) {
scanf("%d", &x);
ins(getIDbyPos(i, j), getIDbyPos(i + 1, j), x);
}
}
for (int i = 1; i <= n - 1; i++) {
for (int x, j = 1; j <= m - 1; j++) {
scanf("%d", &x);
ins(getIDbyPos(i, j), getIDbyPos(i + 1, j + 1), x);
}
}
s = 1, t = n * m;
printf("%d\n", dinic());
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
