记录编号	557667	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 方格取数问题	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-11-21 13:20:01	内存使用	0.00 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int INF = 0x3f3f3f3f;
const int maxn = 35;
int fx[] = {0 , -1 , 0 , 1},fy[] = {1 , 0 , -1 , 0};
using namespace std;
struct edge {
	int to,next,cap;
	edge() {
		to = next = cap = 0;
	}
	edge(int to,int next,int cap):to(to),next(next),cap(cap){}
}Edge[maxn * maxn * maxn];
int head[maxn * maxn << 1],num_edge = -1;
inline void add_edge(int from,int to,int flow) {
	Edge[++ num_edge] = edge(to , head[from] , flow);
	head[from] = num_edge;
}
int n,m;
inline bool judge(int x,int y) {
	return x >= 1&&x <= n&&y >= 1&&y <= m;
}
inline int get(int x,int y) {
	return (x - 1) * m + y;
}
queue<int> q;
int level[maxn * maxn << 1],cur[maxn * maxn << 1];
inline bool bfs(int s,int t) {
	memset(level , 0 , sizeof(level));
	q.push(s);
	level[s] = 1;
	while(!q.empty()) {                                         
		int u = q.front();
		q.pop();
		for(int i = head[u];~ i;i = Edge[i].next) {
			int v = Edge[i].to;                             
			if(!level[v]&&Edge[i].cap > 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[t] != 0;
}
inline int dfs(int x,int t,int maxflow) {
	if(x == t||!maxflow)return maxflow;
	int f,flow = 0;
	for(int i = cur[x];~ i;i = Edge[i].next) {
		int v = Edge[i].to;                                
		cur[x] = i;
		if(level[v] == level[x] + 1&&(f = dfs(v , t , min(Edge[i].cap , maxflow)))) {
			if(!f) {
				level[v] = 0;
			}
			Edge[i].cap -= f;
			Edge[i ^ 1].cap += f;             
			flow += f;
			maxflow -= f;
			if(!maxflow)break ;
		}
	}
	return flow;
}
inline int Dinic(int s,int t) {
	int flow = 0;
	while(bfs(s , t)) {
		memcpy(cur , head , sizeof(head));                   
		flow += dfs(s , t , INF);
	}
	return flow;
}
int main() {                   
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	memset(head , -1 , sizeof(head));
	scanf("%d%d",&n,&m);
	int tot = 0;
	int s = n * m + 1,t = n * m + 2;
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= m;++ j) {
			int pos;
			scanf("%d",&pos);
			tot += pos;
			if((i + j) & 1) {
				add_edge(s , get(i , j) , pos);
				add_edge(get(i , j) , s , 0);
				for(int k = 0;k < 4;++ k) {
					int x = fx[k] + i,y = fy[k] + j;
					if(judge(x , y)) {
						add_edge(get(i , j) , get(x , y) , INF);
						add_edge(get(x , y) , get(i , j) , 0);
					}
				}
			}
			else {
				add_edge(get(i , j) , t , pos);                                                          
				add_edge(t , get(i , j) , 0);
			}
		}
	}
	printf("%d",tot - Dinic(s , t));
	fclose(stdin);
	fclose(stdout);
	return 0;
}