题解 P2774 【方格取数问题】

学委 · 2018-12-28 08:38:38 · 题解

限制条件是——如果要取某一个方格，那么禁止取相邻的四个方格，不限制其它所有方格。

所以猜测，从禁止的角度考虑才会更高效。也就是说，先选中所有方格，再想办法删去权值和尽量小的一批方格。

相邻的概念是，横坐标或纵坐标中的一个相差 1，所以两点的横纵坐标之和奇偶性不同。

于是，横纵坐标和的奇偶性相同的两个点肯定不互斥（奇偶性不同的可能互斥）。把互斥的点连边的话，会形成一个二分图。

但先不管这个。

要想办法构造一个模型，它：

• 能删掉一个元素，表示不取这个方格；

• 删掉的代价为方格的权值；

• 要么删掉的总是保证策略最优的，要么能反悔；

• 最终状态为：没有互斥的方格了。

好像能发现对应的模型了，大概是图一类的东西：

• 删掉连向方格的边

• 边权为方格的权值

• 网络流搞一搞

• 割

怎么构造一个合适的图呢？最好能利用上面的二分图。并不容易想到：

源点连向二分图的一个点集（横纵坐标之和为奇数的那些方格），边权为点权。删一条边表示不取这个方格。

二分图的另一个点集连向超级汇，边权还是点权。删边也表示不取此点。

二分图内部的边，连接着互斥的点。边权全部赋为 inf，以保证在最小割中不被删。啥意思？

想象一下通过某种方式，求出了该图最小割。

• 因为是最小割，所以中间的 inf 边没删，删掉的都是源点连出的边，或连入汇点的边。

  因此这个割能够确切表示：不取某些方格。（删掉中间边本来就没有意义，不能表示对方格的操作；只有两侧的边具有意义）

• 因为是割，所以图不连通。不连通，就已经保证没有取到任何互斥的方格（假设图中还有互斥方格，也就是两者在图中各自所属的边还没删，再因为它们中间的 inf 边也没删，所以图还是连通的）

最后只需知道最大流 = 最小割就好了。

//Dinic 理解代价低 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#define N 10010
#define E 100010
#define S 0
#define T (m * n + 1)
#define code(i, j) ((i - 1) * m + j)//点的线性标号 
#define between(x, flo, top) (flo <= x and x <= top)//您是不是不喜欢这个qwq 
int getint() {
    int res = 0, ch = getchar();
    while (!isdigit(ch) and ch != EOF)
        ch = getchar();
    while (isdigit(ch))
        res = res * 10 + (ch - '0'), ch = getchar();
    return res;
}
inline int min(int x, int y) { return (x < y) ? x : y; }
using std::queue;
const int d[4][2] = {//待会枚举四个方向用的 
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0}
};

int m, n;
int sum = 0;

int first[N];
int nxt[E], to[E], val[E], cnt = 1;
void addE(int u, int v, int w) {
    ++cnt;
    to[cnt] = v;
    val[cnt] = w;
    nxt[cnt] = first[u];
    first[u] = cnt;
}

int dep[N];
queue<int> q;
bool bfs() {
    memset(dep, 0, sizeof(dep));

    dep[S] = 1;
    q.push(S);
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        for (int p = first[u]; p; p = nxt[p]) {
            int v = to[p];
            if (dep[v])
                continue;
            if (val[p]) {//放心，开始都是正权的情况下，不会出现负数的 
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[T];
}

int dfs(int u, int in) {
    if (u == T)
        return in;
    int out = 0;
    for (int p = first[u]; p and in; p = nxt[p]) {

        if (val[p] == 0)
            continue;
        int v = to[p];
        if (dep[v] != dep[u] + 1)
            continue;

        int res = dfs(v, min(val[p], in));
        val[p] -= res;
        val[p ^ 1] += res;
        in -= res;
        out += res;
    }

    return out;
}

int main() {
    n = getint(), m = getint();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int w = 0;
            sum += w = getint();//假定全部都取，随后会删 
            if ((i + j) % 2 == 0) {//阵营A，源点连向自己，自己连向阵营B 
                addE(S, code(i, j), w);
                addE(code(i, j), S, 0);

                for (int k = 0; k <= 3; ++k) {
                    int x = i + d[k][0], y = j + d[k][1];
                    if (between(x, 1, n) and between(y, 1, m)) {
                        addE(code(i, j), code(x, y), 2e9);
                        addE(code(x, y), code(i, j), 0);
                    }
                }               
            }
            else {//阵营B，连向汇点 
                addE(code(i, j), T, w);
                addE(T, code(i, j), 0);
            }
        }

    int cut = 0;//最小割 
    while (bfs())
        cut += dfs(S, 2e9);//最小割 = 最大流 
    printf("%d\n", sum - cut);
    return 0;
}