[题解]CF1534F1FallingSand(EasyVersion)

题目链接

#1.0 题目大意

一个网格图，# 表示沙子，. 表示空，你可以选择某些沙子使其掉落，沙子掉落过程中会扰动它下落路径周围四格（上下左右）的沙子，使他们一同掉落，问最少选择几块沙子可以使全部沙子掉落。

#2.0 思路

#2.1 整体想法

考虑将 “扰动” 这一关系转化成边，“扰动” 这一关系是单向的，即若 \(A\) 能扰动 \(B\)，不代表 \(B\) 能扰动 \(A\)。

将图中的 # 用 “扰动” 为边连接后会得到一张有向图，我们发现，在这张图中存在许多强连通分量（SCC），很显然，每一个 \(\text{SCC}\) 中的沙子扰动任意一个，该 \(\text{SCC}\) 中的所有沙子都会掉落，那么我们便可以将每个 \(\text{SCC}\) 看做一个点，即用 \(\text{Tarjan}\) 算法进行缩点。

缩点之后会得到一个有向无环图（DAG），在这张图上，无论如何都不会被扰动的点就是我们要选择的点。那么我们只需要知道这张 \(\text{DAG}\) 中有多少个入度为 \(0\) 的点即可。

下面来看每一步的细节。

#2.2 储存

题目中只给了这样一条对网格大小的限制：

也就是说，\(n\) 和 \(m\) 都有可能达到 \(4\cdot10^5\) 的级别，我们并不能直接开两维大小都是 \(4\cdot10^5\) 的二维数组进行储存。但是，格子的数量范围是确定的，我们可以直接开一维数组 mp[400010] 来储存格子的信息。

转换方法也很简单，将格子 \((i,j)\) 编号为 \((i-1)\cdot m+j\) 即可，其实就是自左而右、自上而下地编号。

inline int get_ind(const int &i,const int &j){
return (i - 1) * m + j;
}


#2.3 建图

找到真正可能出现的 “扰动” 并转化成边是建图的关键。我们来看一个沙子 \(A\) 下落时究竟可能会扰动哪些沙子（假设这些沙子存在）。

• \(A\) 正上方一格的沙子；


• \(A\) 正下方距离最近的沙子；


• \(A\) 左边一列，比 \(A\) 正下方距离最近的沙子高度更高的最高的沙子。


• \(A\) 右边一列，比 \(A\) 正下方距离最近的沙子高度更高的最高的沙子。

上图中，\(A\) 被选中，只有 \(B,C,D,E\) 会被扰动，因为 \(F\) 会被 \(D\) 先扰动，\(G\) 会先被 \(C\) 扰动，正对应了我们上面的四种情况。

当然，假若 \(C\) 不存在，\(G\) 也不会被 \(A\) 扰动，显然 \(B\) 会比 \(A\) 更早接触 \(G.\)

#2.4 缩点 & 统计

缩点正常用 \(\text{Tarjan}\) 缩点即可。

因为我用的链式前向星存图，记录了边的数量，在统计时直接枚举每条边，判断该边两端点是否在同一 \(\text{SCC}\) 中，如果不在，将终点所在的 \(\text{SCC}\) 的入度加一即可。

这里不用去重边，因为入度只要有，再多也是有，入度要没有，咋整也没有。

之后统计入度为 \(0\) 的 \(\text{SCC}\) 的数量即可。

#3.0 代码实现

const int N = 500010;
const int INF = 0x3fffffff;
struct Edge{
int u,v;
int nxt;
};
Edge e[N <<2];
char mp[N];
int n,m,a[N],head[N],cnt = 1,ck[N];
int T,dfn[N],low[N],inst[N],st[N],frt;
int scc[N],scnt,icnt[N],ans;
/*获取格子的编号*/
inline int get_ind(const int &i,const int &j){
return (i - 1) * m + j;
}
/*加边*/
inline void add(const int &u,const int &v){
e[cnt].u = u;
e[cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt ++;
}
inline void tarjan(int x){ // Tarjan 算法缩点
dfn[x] = low[x] = ++ T;
inst[x] = true;st[++ frt] = x;
for (int i = head[x];i;i = e[i].nxt)
if (!dfn[e[i].v]){
tarjan(e[i].v);
low[x] = min(low[x],low[e[i].v]);
}
else if (inst[e[i].v])
low[x] = min(low[x],dfn[e[i].v]);
if (dfn[x] == low[x]){
int y = 0;++ scnt;
do{
y = st[frt --];
scc[y] = scnt;
inst[y] = false;
}while (y != x);
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
cin >> mp[get_ind(i,j)];
for (int i = 1;i <= n;i ++)
scanf("%d",&a[i]);
/*建图*/
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++){
if (mp[get_ind(i,j)] == '#'){
ck[get_ind(i,j)] = true;//标记为沙子
if (i > 1 && mp[get_ind(i - 1,j)] == '#')//如果正上方一格有沙子
add(get_ind(i,j),get_ind(i - 1,j));
/*找正下方最近的沙子*/
for (int k = i + 1;k <= n;k ++)
if (mp[get_ind(k,j)] == '#'){
add(get_ind(i,j),get_ind(k,j));
break;
}
/*左边一列，比正下方距离最近的沙子高度更高的最高的沙子*/
if (j > 1) for (int k = i;k <= n && (mp[get_ind(k,j)] != '#' || k == i);k ++)
if (mp[get_ind(k,j - 1)] == '#'){
add(get_ind(i,j),get_ind(k,j - 1));
break;
}
/*右边一列，比正下方距离最近的沙子高度更高的最高的沙子*/
if (j if (mp[get_ind(k,j + 1)] == '#'){
add(get_ind(i,j),get_ind(k,j + 1));
break;
}
}
}
/*找 SCC, 缩点*/
for (int i = 1;i <= n * m;i ++)
if (ck[i] && !dfn[i]) tarjan(i);
for (int i = 1;i if (scc[e[i].u] != scc[e[i].v])
icnt[scc[e[i].v]] ++;//统计入度
for (int i = 1;i <= scnt;i ++)
if (!icnt[i]) ans ++;//统计答案
printf("%d",ans);
return 0;
}


End

希望能给您带来收获。