Description

文理分科是一件很纠结的事情! (虽然看到这个题目的人肯定都没有纠结过)

小 P 所在的班级要进行文理分科. 他的班级可以用一个 \(n \times m\) 的矩阵进行描述, 每个格子代表一个同学的座位. 每位同学必须从文科和理科中选择一科. 同学们在选择科目 的时候会获得一个满意值. 满意值按如下的方式得到:

  1. 如果第 \(i\) 行第 \(j\) 列的同学选择了文科, 则他将获得 \(art[i][j]\) 的满意值, 如果选择理科, 将得到 $science [i] [j] $的满意值.
  2. 如果第 \(i\) 行第 \(j\) 列的同学选择了文科, 并且他相邻 (两个格子相邻当且仅当它们 拥有一条相同的边) 的同学全部选择了文科, 则他会更开心, 所以会增加 \(same\_art[i][j]\) 的满意值.
  3. 如果第 \(i\) 行第 \(j\) 列的同学选择了理科, 并且他相邻的同学全部选择了理科, 则增加 \(same\_science[i][j]\) 的满意值.

小 P 想知道, 大家应该如何选择, 才能使所有人的满意值之和最大. 请告诉他这个最大值.

Input

第一行为两个正整数:\(n, m\)

接下来的 \(4\) 个 \(n \times m\) 的 \(n\) 行 \(m\) 列的由数字构成的矩阵, 分别表示这些 满意值对应的矩阵:\(art[i][j], science[i][j], same\_art[i][j], same\_science[i][j]\).

Output

输出为一个整数, 表示最大的满意值之和

Sample Input

3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4

Sample Output

152

Data Range

\(n, m \leq 100\), 读入数据均 \(\leq 500\)

Explanation

一道最小割题目, 参见 @PoPoQQQ 题解:

http://blog.csdn.net/PoPoQQQ/article/details/43968017

令 \(S\) 集为学文,\(T\) 集为学理

每个人学文或者学理的满意度很好连边

如果某个集合内的人都学理会获得一个满意度, 那么就新加一个点, 将集合内的所有人向这个点连流量为正无穷的边, 再从这个点向 \(T\) 连一条流量为满意度的边, 表示集合内任意一个人学文都要把这个点与 \(T\) 的边割掉

都学文同理

建完图之后跑最小割即可

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 = 40010, maxm = 1000100;
const lli infinit = 0x007f7f7f7f7f7f7f7fll;

const int x_ar[5] = { 0,  0,  0,  1, -1 },
          y_ar[5] = { 0,  1, -1,  0,  0 };

class MixedMaximumFlow
{
public:
    struct edge
    {
        int u, v; lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        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 = 0;
        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;
    }
    lli dfs(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = dfs(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    lli eval(void)
    {
        lli sum = 0;
        while (make_level()) {
            lli tmp = dfs(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n, m;
int pos(int i, int j) {
    return (i-1)*m + j; }
lli tot_sum = 0;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = 3*n*m + 2;
    graph.s = 3*n*m + 1;
    graph.t = graph.n;
    // To learn art, science, respectively
    rep(i, 1, n) rep(j, 1, m) {
        int x; scanf("%d", &x);
        graph.add_edge(graph.s, pos(i, j), x);
        tot_sum += x;
    }
    rep(i, 1, n) rep(j, 1, m) {
        int x; scanf("%d", &x);
        graph.add_edge(pos(i, j), graph.t, x);
        tot_sum += x;
    }
    // To learn art or science, with its adjacencies, respectively
    rep(i, 1, n) rep(j, 1, m) {
        int val; scanf("%d", &val);
        tot_sum += val;
        rep(k, 0, 4) {
            int x = x_ar[k] + i, y = y_ar[k] + j;
            if (x<1 || x>n || y<1 || y>m)
                continue;
            graph.add_edge(pos(i, j) + n*m, pos(x, y), infinit);
        }
        graph.add_edge(graph.s, pos(i, j) + n*m, val);
    }
    rep(i, 1, n) rep(j, 1, m) {
        int val; scanf("%d", &val);
        tot_sum += val;
        rep(k, 0, 4) {
            int x = x_ar[k] + i, y = y_ar[k] + j;
            if (x<1 || x>n || y<1 || y>m)
                continue;
            graph.add_edge(pos(x, y), pos(i, j) + 2*n*m, infinit);
        }
        graph.add_edge(pos(i, j) + 2*n*m, graph.t, val);
    }
    // Evaluating result
    lli res = tot_sum - graph.eval();
    printf("%lld\n", res);
    return 0;
}