题解 P4701 【粘骨牌】

p878567 · 2019-07-15 21:47:58 · 题解

NOI模拟赛前写一份题解攒RP。

PART 1

把所有格子黑白交替染色（不妨规定角上为黑色）：

我们首先观察到

性质1：

空白格子一定是黑格。

性质2：

不论怎样进行移动，同一块骨牌总是盖住相同的白格。

上面两个性质是显然的，这里不进行证明。

考虑白格(x,y)，它总是被某一确定的骨牌a覆盖，且a的方向无法改变。不妨设a确定为横向，那么如果空白格位于(x+1,y),(x-1,y)中的某一格，则它们可以互相到达，且(x,y+1),(x,y-1)不能互相到达。a确定为纵向时也有类似的结论。

现在，我们建一个图，以黑格为顶点建立一个图，边权取固定对应骨牌的代价，如样例3：

同时，我们规定初始的空格子为s。

这样的话，不可能露出格子u \Leftrightarrow s与u间无路径；固定骨牌\Leftrightarrow删除边；代价最小\Leftrightarrow删除的边权最小，于是在图上求最小割？

实际上是可以的，复杂度为O(nm)，复杂度证明见PART 2。

PART 2

为了继续进行下去，我们需要

性质3：

包含s的连通块是一棵树。

这是因为：如果这一连通块中存在环，那么我们可以在棋盘中把空格子绕一圈，在不经过重复路径的前提下回到起点，也就是移动第一块骨牌后该骨牌就不再被移动过，这样的话初始格变不会再露出来，矛盾!

（注：不包含s的连通块不一定是树，但这对解题无影响。）

这样的话，我们可以在包含s的连通块上树形DP（把s看做根，设f_u表示使得从u无法到达u子树内任意特殊节点的最小代价

）

附：最小割的复杂度是基于Dinic算法的，原因是连通块是树表明只需要寻找一次增广路就可以找全。

代码：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int read() {
    char c=getchar();while(!isdigit(c))c=getchar();
    int num=0;while(isdigit(c))num=num*10+c-'0',c=getchar();
    return num;
}
int a[501001];
int x[1002002], y[1002002];
int v[1002][1002];
int t[1002002];
int head[1002002], ver[2004003], edge[2004003], nxt[2004003], size;
void addedge(int u, int v, int w) {
    ver[++size] = v, edge[size] = w, nxt[size] = head[u], head[u] = size;
    ver[++size] = u, edge[size] = w, nxt[size] = head[v], head[v] = size;
}
long long fa[1002002], f[1002002];
bool dfs(int x) {
    if (t[x]) {f[x] = inf;return 0;}
    for (int i = head[x]; i; i = nxt[i])
        if (fa[x] != ver[i]) {
            fa[ver[i]] = x;
            dfs(ver[i]);
            f[x] += min(f[ver[i]], (long long)edge[i]);
        }
    return 1;
} 
int main() {
    int n, m, k;
    n = read(), m = read(), k = read();
    for (int i = 1; i <= (n*m-1)/2; i++) a[i] = read();
    for (int i = 1; i <= k; i++) x[i] = read(), y[i] = read(), t[(x[i]-1)*m+y[i]] = 1;
    int x0, y0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            v[i][j] = read();
            if (i >= 2 && v[i][j] == v[i-1][j]) {
                if (i+j&1) {if(i<n)addedge(i*m+j,(i-2)*m+j, a[v[i][j]]);}
                else {if(i>2)addedge((i-1)*m+j, (i-3)*m+j, a[v[i][j]]);};
            }
            if (j >= 2 && v[i][j] == v[i][j-1]) {
                if (i+j&1) {if(j<m)addedge((i-1)*m+j+1, (i-1)*m+j-1, a[v[i][j]]);}
                else {if(j>2)addedge((i-1)*m+j, (i-1)*m+j-2, a[v[i][j]]);};
            }
            if (v[i][j] == 0) x0 = i, y0 = j;
        }
    if (dfs((x0-1)*m+y0)) cout << f[(x0-1)*m+y0] << endl;
    else cout << "GG" << endl;
}