Description

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

Input

输入第一行为两个整数, 分别为正整数 \(n\) 和 \(m\), 分别表示区域的行数和列数;

第 \(2\) 到 \(n+1\) 列, 每行 \(m\) 个整数, 表示商业区收益矩阵 \(A\);

第 \(n+2\) 到 \(2n+1\) 列, 每行 \(m\) 个整数, 表示工业区收益矩阵 \(B\);

第 \(2n+2\) 到 \(3n+1\) 行, 每行 \(m\) 个整数, 表示相邻额外收益矩阵 \(C\).

Output

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

Sample Input

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

Sample Output

81

Data Range

对于所有数据, 满足:\(n, m \leq 100\), 且所有输入的数字不超过 \(1000\).

Explanation

一看就是把节点割成两半的最小割问题对吧......

所以黑白染色然后做一个经典最小割建图就可以了~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 100100, maxN = 110;
const int infinit = 0x7fffffff;

const int movx[4] = {0, 0, 1, -1},
          movy[4] = {1, -1, 0, 0};

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, int flow, int rflow = 0)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u; q->flow = rflow;
        q->next = edges[v]; edges[v] = q;
        p->rev = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        queue<int> que;
        memset(level, 0, sizeof(level));
        que.push(s);
        level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] != 0)
            return true;
        return false;
    }
    int dfs(int p, int mn)
    {
        if (p == t)
            return mn;
        int sum = 0, tmp;
        for (edge *ep = edges[p]; sum < mn && ep; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = dfs(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    sum += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    int eval(void)
    {
        int sum = 0, tmp;
        while (make_level()) {
            tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n, m;
int a[maxN][maxN], b[maxN][maxN], c[maxN][maxN];
int colour[maxN][maxN];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    rep(i, 1, n) rep(j, 1, m)
        scanf("%d", &a[i][j]);
    rep(i, 1, n) rep(j, 1, m)
        scanf("%d", &b[i][j]);
    rep(i, 1, n) rep(j, 1, m)
        scanf("%d", &c[i][j]);
    // B&W colorizing table
    rep(i, 1, n) rep(j, 1, m)
        colour[i][j] = (i+j) & 1;
    // Converting adjacency table to graph (or so it looks like)
    graph.n = n*m + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    #define pos(_a,_b) (((_a)-1)*m+(_b))
    int sum = 0;
    rep(i, 1, n) rep(j, 1, m) {
        if (colour[i][j])
            swap(a[i][j], b[i][j]);
        graph.add_edge(graph.s, pos(i, j), a[i][j]);
        graph.add_edge(pos(i, j), graph.t, b[i][j]);
        sum += a[i][j] + b[i][j];
        if (colour[i][j]) rep(k, 0, 3) {
            int cx = i + movx[k],
                cy = j + movy[k];
            if (cx < 1 || cx > n || cy < 1 || cy > m)
                continue;
            int flow = c[i][j] + c[cx][cy];
            graph.add_edge(pos(i, j), pos(cx, cy), flow, flow);
            sum += flow;
        }
    }
    int res = sum - graph.eval();
    printf("%d\n", res);
    return 0;
}