记录编号	434186	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]圈地计划	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-08-07 12:02:44	内存使用	1.75 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
#define MAXN 10010
using namespace std;
struct Edge {
	int t, next, v;
}e[100000];
int N, M, S, T, head[MAXN], cnt = 1, dis[MAXN], A[110][110], B[110][110], C[110][110], cur[MAXN], num[110][110];
void Add_Edge(int from, int to, int cap) {
	e[++cnt].t = to;e[cnt].next = head[from];head[from] = cnt;e[cnt].v = cap;
	e[++cnt].t = from;e[cnt].next = head[to];head[to] = cnt;e[cnt].v = 0;
}
bool BFS() {
	memset(dis, -1, sizeof(dis));
	queue<int>q;
	q.push(S);dis[S] = 0;
	while (!q.empty()) {
		int u = q.front();q.pop();
		for (int i = head[u];i;i = e[i].next) {
			if (e[i].v&&dis[e[i].t] == -1) {
				dis[e[i].t] = dis[u] + 1;
				q.push(e[i].t);
			}
		}
	}
	return dis[T] != -1;
}
int DFS(int u, int now) {
	if (u == T)return now;
	int f, flow = 0;
	for (int &i = cur[u];i;i = e[i].next) {
		if (e[i].v&&dis[e[i].t] == dis[u] + 1 && (f = DFS(e[i].t, min(e[i].v, now - flow)))) {
			e[i].v -= f;e[i ^ 1].v += f;flow += f;
			if (flow == now)return flow;
		}
	}
	if (!flow)dis[u] = -1;
	return flow;
}
int main() {
	freopen("nt2011_land.in", "r", stdin);
	freopen("nt2011_land.out", "w", stdout);
	scanf("%d%d", &N, &M);
	int sum = 0;
	S = 0;T = N*M + 1;
	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= M;j++) {
			scanf("%d", &A[i][j]);
			sum += A[i][j];
		}
	}
	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= M;j++) {
			scanf("%d", &B[i][j]);
			sum += B[i][j];
		}
	}
	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= M;j++) {
			scanf("%d", &C[i][j]);
			num[i][j] = (i - 1)*M + j;
		}
	}
	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= M;j++) {
			if (!((i + j) & 1)) {
				Add_Edge(S, num[i][j], A[i][j]);
				Add_Edge(num[i][j], T, B[i][j]);
				if (i - 1 >= 1)Add_Edge(num[i][j], num[i - 1][j], C[i][j] + C[i - 1][j]), Add_Edge(num[i - 1][j], num[i][j], C[i][j] + C[i - 1][j]), sum += C[i][j] + C[i - 1][j];
				if (j - 1 >= 1)Add_Edge(num[i][j], num[i][j - 1], C[i][j] + C[i][j - 1]), Add_Edge(num[i][j - 1], num[i][j], C[i][j] + C[i][j - 1]), sum += C[i][j] + C[i][j - 1];
				if (i + 1 <= N)Add_Edge(num[i][j], num[i + 1][j], C[i][j] + C[i + 1][j]), Add_Edge(num[i + 1][j], num[i][j], C[i][j] + C[i + 1][j]), sum += C[i][j] + C[i + 1][j];
				if (j + 1 <= M)Add_Edge(num[i][j], num[i][j + 1], C[i][j] + C[i][j + 1]), Add_Edge(num[i][j + 1], num[i][j], C[i][j] + C[i][j + 1]), sum += C[i][j] + C[i][j + 1];
			}
			else {
				Add_Edge(S, num[i][j], B[i][j]);
				Add_Edge(num[i][j], T, A[i][j]);
			}
		}
	}
	int ans = 0;
	while (BFS()) {
		memcpy(cur, head, sizeof(head));
		ans += DFS(S, INF);
	}
	printf("%d", sum - ans);
	return 0;
}