标题效果：鉴于加权值矩阵，带走一个地方的权利值之后，与其相邻的格儿童权利值变0。问多少可以取出到右值。

思维：Amber论文题目。不难建设，图着色。颜色从S连边，还有一种颜色向T连边。再把相邻的格子连边。之后跑最小割，用总权值减去最大流就是答案。

CODE：

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 400

#define MAXP 40000

#define MAXE 500010

#define INF 0x3f3f3f3f

#define S 0

#define T 39999

using namespace std;

const int dx[] = {0,1,0,-1,0};

const int dy[] = {0,0,1,0,-1};

int m,n,cnt;

int src[MAX][MAX],num[MAX][MAX];

int head[MAXP],total = 1;

int next[MAXE],aim[MAXE],flow[MAXE];

int deep[MAXP];

inline void Add(int x,int y,int f)

{

	next[++total] = head[x];

	aim[total] = y;

	flow[total] = f;

	head[x] = total;

}

bool BFS()

{

	static queue<int> q;

	while(!q.empty())	q.pop();

	memset(deep,0,sizeof(deep));

	deep[S] = 1;

	q.push(S);

	while(!q.empty()) {

		int x = q.front(); q.pop();

		for(int i = head[x]; i; i = next[i])

			if(flow[i] && !deep[aim[i]]) {

				deep[aim[i]] = deep[x] + 1;

				q.push(aim[i]);

				if(aim[i] == T)	return true;

			}

	}

	return false;

}

int Dinic(int x,int f)

{

	if(x == T)	return f;

	int temp = f;

	for(int i = head[x]; i; i = next[i])

		if(flow[i] && deep[aim[i]] == deep[x] + 1 && temp) {

			int away = Dinic(aim[i],min(temp,flow[i]));

			if(!away)	deep[aim[i]] = 0;

			flow[i] -= away;

			flow[i^1] += away;

			temp -= away;

		}

	return f - temp;

}

int main()

{

	cin >> m >> n;

	int sum = 0;

	for(int i = 1; i <= m; ++i)

		for(int j = 1; j <= n; ++j) {

			scanf("%d",&src[i][j]);

			sum += src[i][j];

			num[i][j] = ++cnt;

			if((i + j)&1)

				Add(S,num[i][j],src[i][j]),Add(num[i][j],S,0);

			else

				Add(num[i][j],T,src[i][j]),Add(T,num[i][j],0);

		}

	for(int i = 1; i <= m; ++i)

		for(int j = 1; j <= n; ++j) {

			if(((i + j)&1) == 0)	continue;

			for(int k = 1; k <= 4; ++k) {

				int fx = i + dx[k];

				int fy = j + dy[k];

				if(!fx || !fy || fx > m || fy > n)	continue;

				Add(num[i][j],num[fx][fy],INF);

				Add(num[fx][fy],num[i][j],0);

			}

		}

	int max_flow = 0;

	while(BFS())

		max_flow += Dinic(S,INF);

	cout << sum - max_flow << endl;

	return 0;

}