题目描述

最近房地产商 GDOI(Group of Dumbbells Or Idiots) 从 NOI(Nuts Old Idiots) 手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为 $N×M$ 块小区域。GDOI 要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第 $i$ 行第 $j$ 列的区域，建造商业区将得到 $A_{ij}$ 的收益，建造工业区将得到 $B_{ij}$ 的收益。另外不同的区域连在一起可以得到额外的收益，即如果区域 $(i,j)$ 相邻（相邻是指两个格子有公共边）有 $K$ 块（显然 $K$ 不超过 $4$ ）类型不同于 $(i,j)$ 的区域，则这块区域能增加 $k×C_{ij}$ 收益。经过 Tiger.S 教授的勘察，收益矩阵 $A,B,C$ 都已经知道了。你能帮 GDOI 求出一个收益最大的方案么？

输入格式

输入第一行为两个整数，分别为正整数 $N$ 和 $M$ ，分别表示区域的行数和列数；

第 $2$ 到 $N+1$ 列，每行 $M$个整数，表示商业区收益矩阵 $A$ ；

第 $N+2$ 到 $2N+1$ 列，每行 $M$ 个整数，表示工业区收益矩阵 $B$ ；

第 $2N+2$ 到 $3N+1$行，每行 $M$ 个整数，表示相邻额外收益矩阵 $C$ 。

输出格式

输出只有一行，包含一个整数，为最大收益值。

输入样例

3 3
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
1 1 1
1 3 1
1 1 1

输出样例

81

数据范围与约定

$N,M\leq 100$，$0\leq A_{i,j},B_{i,j},C_{i,j}\leq 10^{3}$ 。

对于 $30\%$ 的数据有 $N, M\leq 6$；

对于 $50\%$ 的数据有 $N, M \leq 20$；

对于 $100\%$ 的数据有 $N,M\leq 100$。

提示

数据已加强，并重测 -- 2015.5.15

Solution

每个点有两种选择，显然考虑最小割模型。

首先考虑最简单的模型一，即每个点仅有 $a,b$ 两种选择收益，没有额外的收益 $c$ 。如图一所示，显然我们直接建虚拟源点 $S$ 和虚拟汇点 $T$，对于任意一点 $1$，向 $S$ 连权值为 $a[1]$ 的边，表示选择方案 $a$ ，向 $T$ 连权值为 $b[1]$ 的边，表示选择方案 $b$，由于每一个点只能有一种选择方案，所以我们只需要割掉一些边，使得 $S,T$ 不连通即可，我们直接求最小割，总边权值减去最小割既是剩余的最大收益。

图一

考虑加上题目中的收益 $c$，题目中的收益 $c$ 是相邻点之间方案选择不同才会拥有的附加收益，我们这里先考虑一个简化版问题，即某些给定点对 $(u,v)$之间方案选择相同才会拥有附加收益，同为 $a$ 则获得收益 $c_a(u,v)$，同为 $b$ 则获得收益 $c_b(u,v)$，也即模型二，P1361 小M的作物 。

我们发现此时需要相同的方案选择，也即对于图一中的两点 $1$ 和 $2$，当且仅当 $b[1]$ 边和 $b[2]$ 边同时割掉之后，也即图二所示，此时可以获得额外收益 $c(1,2)$，割掉两边之后，此时 $S,T$ 不连通，两点选择方案有且仅有一个，符合题意，此时剩余的所有边权是我们获得的收益，我们可以加上额外收益 $c(1,2)$，为了保证当且仅当此时我们才能加上收益 $c$，可以建虚拟源点 $x$，$S$ 到 $x$ 连权值为 $c_a(1,2)$ 的边，此时我们就可以额外获得收益 $c_a(1,2)$，为了防止 $(x,1),(x,2)$ 被意外割掉不符合题意，我们将其边权设为 $INF$ 即可。

图二

综上所述，我们建如图三的模型，总权值减去最小割即为答案。

图三

回到本题的模型三，本题中，每个点相邻的点（上下左右显然最多有 $4$ 个），选择不同的方案才能获得收益 $c$。

首先处理可以获得收益 $c$ 的点集，要求为相邻，显然对图进行黑白染色，即可得到可以获得收益 $c$ 的点集方案。此时问题和模型二的差别仅为方案相同和不同。为了将模型三转化为模型二，我们将该条件转变即可，所以就我们可以直接将所有黑色点的收益 $a$ 和收益 $b$ 交换，不同的条件就直接转化为了相同，问题显然就转化成了模型二，直接建图三跑最小割即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define num(i, j) ((i - 1) * m + j)

using ll = long long;
const int INF = 1e18, maxn = 5e5 + 7, maxm = 5e6 + 7, maxv = 2e3 + 7;

int ans;
int head[maxn], nex[maxm], ver[maxm], tot;
ll edge[maxm];
int n, m, s, t, n_cnt; 
ll maxflow;
ll deep[maxn]; 
int now[maxm]; 
queue <int> q;
int a[maxv][maxv], b[maxv][maxv], c[maxv][maxv];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

inline void add(int x,int y,int z){
    ver[tot] = y; edge[tot] = z; nex[tot] = head[x]; head[x] = tot ++ ;
    ver[tot] = x; edge[tot] = 0; nex[tot] = head[y]; head[y] = tot ++ ;
}

inline bool bfs() { 
    for(int i = 0; i <= n_cnt; ++ i)
		deep[i] = INF, now[i] = head[i]; 
    while(!q.empty())
		q.pop(); 
    q.push(s);
	deep[s] = 0;

    while(!q.empty()){
        int x = q.front();
		q.pop();
        for(int i = head[x]; ~i; i = nex[i]){
            int y = ver[i];
            if(edge[i] > 0 && deep[y] == INF){ 
                q.push(y);
                
                deep[y] = deep[x] + 1;
                if(y == t)return 1; 
            }
        }
    }
    return 0;
}

ll dfs(int x, ll flow) {
    if(x == t)
		return flow;
    ll ans = 0, k, i; 
    for(i = now[x]; ~i && flow; i = nex[i]){
        now[x] = i; 
        int y = ver[i];
        if(edge[i] > 0 && (deep[y] == deep[x] + 1)){  
            k = dfs(y,min(flow,edge[i])); 
            if(!k)deep[y] = INF; 
            edge[i] -= k; 
            edge[i ^ 1] += k; 
            ans += k;
            flow -= k;
        } 
    } 
    return ans;
}

void dinic() {
    while(bfs())
        maxflow += dfs(s,INF);
}

signed main()
{
	memset(head, -1, sizeof head);
	maxflow = 0;
	ans = 0;
	scanf("%lld%lld", &n, &m);
	n_cnt = n * m;
	s = ++ n_cnt, t = ++ n_cnt;

	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			scanf("%lld", &a[i][j]);
			ans += a[i][j];
		}
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			scanf("%lld", &b[i][j]);
			ans += b[i][j];
		}
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			scanf("%lld", &c[i][j]);
		}
	}

	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
			if((i + j) & 1)
				swap(a[i][j], b[i][j]);

	for (int i = 1; i <= n; ++ i) {
	 	for (int j = 1; j <= m; ++ j) {
	 		add(s, num(i, j), a[i][j]);
	 		add(num(i, j), t, b[i][j]);
	 	}
	}

	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			for (int k = 0; k < 4; ++ k) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if(nx <= 0 || nx > n || ny <= 0 || ny > m) 
					continue;
				int x = ++ n_cnt;
				int y = ++ n_cnt;
				ans += 2 * c[i][j];
				add(s, x, c[i][j]);
				add(x, num(i, j), INF);
				add(x, num(nx, ny), INF);
				add(num(i, j), y, INF);
				add(num(nx, ny), y, INF);
				add(y, t, c[i][j]);
			}
		}
	}
	dinic(); 
	ans -= maxflow;
	cout << ans << endl;
	return 0;
}