自动搬运

查看原文

来自洛谷，原作者为

	p878567 以下证明：这一算法的时空复杂度是 $o(+\infty)$

搬运于2025-08-24 22:02:45，当前版本为作者最后更新于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$子树内任意特殊节点的最小代价

$$f_u=\begin{cases}\infty&(u\text{为特殊方格})\\\sum\{\min(f_v,w(u,v)):v\text{为}u\text{的儿子}\}&(u\text{不为特殊方格})\end{cases} $$

）

附：最小割的复杂度是基于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;
}