题解 P6008 【[USACO20JAN]Cave Paintings P】
Vocalise
2020-10-25 13:54:40
奇怪的联通性 DP...
一句话题意：给定网格图，求满足物理原理的空白部分填充方案数。
行数列数 $n,m\le 1000$。
这里的物理原理大概包括两条：重力作用原理和连通器原理~~好像是一个东西~~。
一个原始的想法是从下向上 DP。
但是方格之间有支配关系。考虑以下一个例子：
```
#####
#...#
#.#.#
#...#
#####
```
答案为 $4$，显然观察得到上层的方格一定支配下层方格，一共 $3$ 层。
但是我们从此得知，两个方格的是否关联要基于 $2$ 个因素：
1. 在一个联通块中；
2. 支配者层数相同或高于被支配的方格。
所以我们考虑从下向上维护并查集。
状态的转移在这里却是比较平凡的。
对于一个方格 $(x,y)$ 代表的在 $x$ 层及以下的连通块中，若干**可以联通**且层数多 $1$ 的联通块代表元素的集合为 $S$。
注意，$S$ 中元素在 $x$ 层上是联通的，但是在 $x+1$ 层上是不联通的。
有：
$$ f_{x,y} = 1+\prod_{(i,j)\in S}f_{i,j} $$
因为如果 $(x,y)$ 充水，就只有一种情况，否则 $S$ 中块互不干扰。
所以有了 $\mathcal O(nm)$ 次并查集 `find` 操作复杂度的解法。
具体实现中:
从下到上枚举每一行 $x$。
首先存下 $x+1$ 的所有点在并查集中的父亲。（代表下文「合并前的并查集」。）
然后对于 $x$ 行的空点，合并与其连通的所有点。（即「合并后的并查集」。）
再枚举 $x+1$ 行所有空点，如果它在合并后的并查集中的祖先在 $x$ 行，则说明它对目前答案有贡献，用它在合并前的并查集中的祖先更新合并后的并查集的祖先。
注意这里每个合并前的祖先只能贡献一次。
然后对 $x$ 行所有点 $f$ 值 $+1$。
这里有并查集合并前与合并后之分，是难理解的地方。
最后答案是所有连通块的答案之积。
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
const int N = 1001;
const int NODE = N * N;
const int p = 1000000007;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9');
return x * f;
}
inline int readchar() {
char ch = getchar();
while(ch != '#' && ch != '.') ch = getchar();
return ch;
}
int n,m; char map[N][N];
struct Point {
int x,y;
Point() {}
Point(int _x,int _y): x(_x), y(_y) {}
friend bool operator ==(const Point &x,const Point &y) {
return x.x == y.x && x.y == y.y;
}
};
Point fa[N][N]; int fa1[N];
int vis[N][N],f[N][N];
Point find(Point x) {
if(fa[x.x][x.y] == x) return x;
return fa[x.x][x.y] = find(fa[x.x][x.y]);
}
int find1(int x) {
if(fa1[x] == x) return x;
return fa1[x] = find1(fa1[x]);
}
void Join(Point x,Point y) {
x = find(x), y = find(y);
fa[y.x][y.y] = x;
}
int main() {
n = read(), m = read();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++) {
map[i][j] = readchar();
fa[i][j] = Point(i,j);
}
for(int i = n - 1;i >= 1;i--) {
for(int j = 1;j <= m;j++) fa1[j] = fa[i + 1][j].y, vis[0][j] = false;
for(int j = 1;j <= m;j++) if(map[i][j] == '.') {
f[i][j] = 1;
if(map[i + 1][j] == '.') Join(Point(i,j),Point(i + 1,j));
if(map[i][j - 1] == '.') Join(Point(i,j),Point(i,j - 1));
if(map[i][j + 1] == '.') Join(Point(i,j),Point(i,j + 1));
}
for(int j = 1;j <= m;j++) if(map[i + 1][j] == '.') {
Point F = find(Point(i + 1,j));
if(F.x != i) continue;
int F1 = find1(j);
if(vis[0][F1]) continue;
vis[0][F1] = true;
f[i][F.y] = 1ll * f[i][F.y] * f[i + 1][F1] % p;
}
for(int j = 1;j <= m;j++) if(map[i][j] == '.') f[i][j]++;
// for(int i = 1;i <= n;i++, std::puts(""))
// for(int j = 1;j <= m;j++) std::printf("%d ",f[find(Point(i,j)).x][find(Point(i,j)).y]);
// std::puts("");
}
int ans = 1;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++) if(map[i][j] == '.') {
Point F = find(Point(i,j));
if(vis[F.x][F.y]) continue;
vis[F.x][F.y] = true;
ans = 1ll * ans * f[F.x][F.y] % p;
}
std::printf("%d ",ans);
return 0;
}
```