记录编号	484226	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 方格取数问题	最终得分	100
用户昵称	panda_2134	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2018-01-22 17:08:31	内存使用	1.08 MiB

//发现要用到复杂（超过6个符号）的位运算时马上住手，改用循环预处理！虽然慢一点，但是不会错！
#include <bits/stdc++.h>
 
using namespace std;
 
struct Edge {
	int v, flow, cap, next;
};
 
const int MAXN = 10002, MAXM = 4e4, INF = 0x3f3f3f3f;
const int di[] = { 1, -1, 0, 0 }, dj[] = { 0, 0, 1, -1 };
int R, C, N, M, S, T, Tot, e_ptr=1, head[MAXN+10]; Edge E[(MAXM<<1)+10];
int ID[110][110];
void AddEdge(int u, int v, int cap) {
	E[++e_ptr] = (Edge) { v, 0, cap, head[u] }; head[u] = e_ptr;
	E[++e_ptr] = (Edge) { u, 0, 0,   head[v] }; head[v] = e_ptr;
}
 
int d[MAXN+10], cur[MAXN+10];
bool BFS() {
	queue<int> Q;
	memset(d, 0xff, sizeof(d));
	Q.push(S); d[S] = 0;
	while(!Q.empty()) {
		int u = Q.front(); Q.pop();
		for(int j=head[u]; j; j=E[j].next) {
			int v = E[j].v, f = E[j].flow, c = E[j].cap;
			if(f<c && d[v] == -1) {
				d[v] = d[u] + 1;
				if(v == T) return true;
				else Q.push(v);
			}
		}
	}
	return false;
}
 
int DFS(int u, int flow) {
	if(u == T || flow == 0) return flow;
	int res = flow;
	for(int &j=cur[u]; j; j=E[j].next) {
		int v = E[j].v, f = E[j].flow, c = E[j].cap;
		if(d[v] == d[u] + 1) {
			int tmp = DFS(v, min(res, c-f));
			res -= tmp;
			E[j].flow += tmp;
			E[j^1].flow -= tmp;
		}
	}
	return flow - res;
}
 
int Dinic() {
	int MaxFlow = 0, CurFlow = 0;
	while(BFS()) {
		for(int i=1; i<=N; i++)
			cur[i] = head[i];
		while( (CurFlow = DFS(S, INF)) != 0 )
			MaxFlow += CurFlow;
	}
	return MaxFlow;
}
 
inline bool valid(int i, int j) {
	return i>=1 && i<=R && j>=1 && j<=C;
}
 
void Label() {
	int idx = 0;
	for(int i=1; i<=R; i++) 
		for(int j = 2 - (i&1); j<=C; j+=2)
			ID[i][j] = ++idx;
	for(int i=1; i<=R; i++)
		for(int j = 1 + (i&1); j<=C; j+=2)
			ID[i][j] = ++idx;
}
 
void Init() {
	int Cur;
	scanf("%d%d", &R, &C);
	N = R*C + 2; S = R*C + 1; T = R*C + 2;
	Label();
	for(int i=1; i<=R; i++) 
		for(int j=1; j<=C; j++) {
			scanf("%d", &Cur); Tot += Cur;
			if(((i^j)&1) == 0) {
				AddEdge(S, ID[i][j], Cur);
				for(int t=0; t<4; t++) {
					int ni = i + di[t], nj = j + dj[t];
					if(!valid(ni, nj)) continue;
					AddEdge(ID[i][j], ID[ni][nj], INF);
				}
			} else 
				AddEdge(ID[i][j], T, Cur);
		}
}
 
void Work() {
	printf("%d", Tot - Dinic());
}
 
int main() {
	freopen("grid.in", "r", stdin);
	freopen("grid.out", "w", stdout);
	Init(); Work();
	return 0;
}