Description

高一一班的座位表是个 \(n \times m\) 的矩阵, 经过一个学期的相处, 每个同学和前后左右相邻的同学互相成为了好朋友. 这学期要分文理科了, 每个同学对于选择文科与理科有着自己的喜悦值, 而一对好朋友如果能同时选文科或者理科, 那么他们又将收获一些喜悦值. 作为计算机竞赛教练的 scp 大老板, 想知道如何分配可以使得全班的喜悦值总和最大.

Input

第一行两个正整数 \(n, m\). 接下来是六个矩阵:

第一个矩阵为 \(n\) 行 \(m\) 列, 此矩阵的第 \(i\) 行第 \(j\) 列的数字表示座位在第 \(i\) 行第 \(j\) 列的同学选择文科获得的喜悦值;

第二个矩阵为 \(n\) 行 \(m\) 列, 此矩阵的第 \(i\) 行第 \(j\) 列的数字表示座位在第 \(i\) 行第 \(j\) 列的同学选择理科获得的喜悦值;

第三个矩阵为 \(n-1\) 行 \(m\) 列, 此矩阵的第 \(i\) 行第 \(j\) 列的数字表示座位在第 \(i\) 行第 \(j\) 列的同学与第 \(i+1\) 行第 \(j\) 列的同学同时选择文科获得的额外喜悦值;

第四个矩阵为 \(n-1\) 行 \(m\) 列, 此矩阵的第 \(i\) 行第 \(j\) 列的数字表示座位在第 \(i\) 行第 \(j\) 列的同学与第 \(i+1\) 行第 \(j\) 列的同学同时选择理科获得的额外喜悦值;

第五个矩阵为 \(n\) 行 \(m-1\) 列, 此矩阵的第 \(i\) 行第 \(j\) 列的数字表示座位在第 \(i\) 行第 \(j\) 列的同学与第 \(i\) 行第 \(j+1\) 列的同学同时选择文科获得的额外喜悦值;

第六个矩阵为 \(n\) 行 \(m-1\) 列, 此矩阵的第 \(i\) 行第 \(j\) 列的数字表示座位在第 \(i\) 行第 \(j\) 列的同学与第 \(i\) 行第 \(j+1\) 列的同学同时选择理科获得的额外喜悦值.

Output

输出一个整数, 表示喜悦值总和的最大值.

Sample Input

1 2
1 1
100 110
1
1000

Sample Output

1210

Data Range

对于 100% 的数据, 满足 \(n, m \leq 100\), 所有喜悦值均为小于等于 \(5000\) 的非负整数.

Explanation

相当于把这些学生割成两个部分, 一个部分文科, 另一个部分理科, 然后在文科和文科之间连边、理科和理科之间连边、文科和理科之间连边、理科和文科之间连边. 权值均为矩阵中输入的数据.

既然是求最大喜悦值, 那么要割掉的就是最小的不喜悦值.

写完这破题以后整个人都最小割了...... 光看输入数据就吐了好不好啊 QwQ

Source Code


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

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define rep_2d(_var1,_begin1,_end1,_var2,_begin2,_end2) rep(_var1,_begin1,_end1)rep(_var2,_begin2,_end2)
using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 300100, maxN = 110;
const int infinit = 0x3f3f3f3f;

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 rev_flow=0)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = rev_flow;
        q->next = edges[v]; edges[v] = 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 find(int p, int mn)
    {
        if (p == t)
            return mn;
        int sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = find(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    int eval(void)
    {
        int sum = 0, tmp;
        while (make_level()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n, m, sum;
int a[maxN][maxN], b[maxN][maxN], id[maxN][maxN];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    // Inputting a lot of numbers
    rep_2d(i, 1, n, j, 1, m)
        scanf("%d", &a[i][j]),
        sum += a[i][j],
        a[i][j] *= 2;
    rep_2d(i, 1, n, j, 1, m)
        scanf("%d", &b[i][j]),
        sum += b[i][j],
        b[i][j] *= 2;
    rep_2d(i, 1, n, j, 1, m)
        id[i][j] = (i - 1) * m + j;
    // Building a lot of edges
    int tmp = 0;
    graph.n = n * m + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    rep_2d(i, 1, n - 1, j, 1, m) {
        scanf("%d", &tmp); sum += tmp;
        a[i][j] += tmp; a[i+1][j] += tmp;
        graph.add_edge(id[i][j], id[i+1][j], tmp, tmp);
    } rep_2d(i, 1, n - 1, j, 1, m) {
        scanf("%d", &tmp); sum += tmp;
        b[i][j] += tmp; b[i+1][j] += tmp;
        graph.add_edge(id[i][j], id[i+1][j], tmp, tmp);
    } rep_2d(i, 1, n, j, 1, m - 1) {
        scanf("%d", &tmp); sum += tmp;
        a[i][j] += tmp; a[i][j+1] += tmp;
        graph.add_edge(id[i][j], id[i][j+1], tmp, tmp);
    } rep_2d(i, 1, n, j, 1, m - 1) {
        scanf("%d", &tmp); sum += tmp;
        b[i][j] += tmp; b[i][j+1] += tmp;
        graph.add_edge(id[i][j], id[i][j+1], tmp, tmp);
    } rep_2d(i, 1, n, j, 1, m) {
        graph.add_edge(graph.s, id[i][j], a[i][j]);
        graph.add_edge(id[i][j], graph.t, b[i][j]);
    }
    // Now generating execution
    int res = sum - graph.eval() / 2;
    printf("%d\n", res);
    // Whole lot finished
    return 0;
}