岛屿题 - 题解

标签与难度

标签: Kruskal重构树, 可撤销并查集, 离线算法, 图论, 最大瓶颈路, 最小割, 广度优先搜索, BFS 难度: 2900

题目大意喵~

主人你好喵~ 这是一道有点复杂的图论题哦，让本喵来给你梳理一下吧！

我们拿到了一张 $N \times M$ 的地图，上面有三种地形：

• #: 岛屿，我们不能走上去。
• .: 空地，可以自由行走。
• v: 火山，也可以走上去。

接下来会有 $Q$ 次询问，每次都给一个起点 (r, c)。对于每次询问，我们需要找到一条从 (r, c) 出发、最后又回到 (r, c) 的路径，这条路径需要满足两个条件：

1. 合法性: 路径上的每一步都只能在地图内，并且不能经过岛屿 #。注意，我们可以重复走过一个点或者一条边哦。
2. 包围性: 这条路径必须把所有的岛屿都“围起来”。具体来说，就是如果我们把路径上经过的所有点都从地图上“删除”，那么任何一个岛屿格子都不能通过八个方向（上、下、左、右、左上、左下、右上、右下）连接到地图的边界。

对于这样一条“包围路径”，我们定义它的权值为：路径上所有点的“点权”的最小值。而一个点的“点权”被定义为它到最近的火山的曼哈顿距离。

我们的目标是，对于每个给定的起点 (r, c)，找到一条满足条件的包围路径，使得它的路径权值最大！然后输出这个最大的权值。

听起来是不是有点绕？没关系，跟着本喵的思路一步步来，很快就能搞定啦，喵~

解题思路分析

这道题的核心是“最大化最小值”，这是一个非常经典的信号，通常指向二分答案或者像本题解法中用到的 Kruskal 重构树~。让我们来一步步拆解这个问题吧！

第一步：点权预处理

首先，我们需要知道地图上每个格子的点权，也就是它到最近火山的曼哈顿距离。这是一个典型的多源最短路问题。因为网格图上的边权都是1，所以我们可以用一次多源广度优先搜索（Multi-source BFS） 来解决。

具体做法是：

1. 创建一个 dist[N][M] 数组，初始化为无穷大。
2. 将所有火山 v 的位置放入一个队列中，并将它们的 dist 值设为 0。
3. 像普通 BFS 一样，不断从队列中取出点，并向其四方向的邻居扩展，更新它们的 dist 值。

这样，BFS 结束后，dist[i][j] 就存储了点 (i, j) 到最近火山的曼哈ton距离啦，这就是它的点权！我们之后称之为 val(u)。

第二步：理解“包围”的真正含义

“包围”这个词听起来很形象，但在算法里我们需要一个更精确的定义。题目说，移除路径上的点后，岛屿和边界就分开了。这其实是在描述一个割（Cut）的概念。

我们可以把问题模型化：

1. 建立一个包含所有格子的八连通图（因为连通性是八方向的）。
2. 设置一个超级源点 S，将它与所有边界格子相连。
3. 设置一个超级汇点 T，将它与所有岛屿 # 格子相连。

现在，“包围所有岛屿”就等价于：找到一个点集（也就是我们的路径），从图中移除这个点集后，S 和 T 不再连通。这样的点集被称为 S-T 点割。

我们的路径必须是一个 S-T 点割，并且要包含给定的起点 (r, c)。

第三步：从“最大化最小值”到 Kruskal 重构树

我们的目标是最大化路径的权值，也就是 max(min(val(u))) for u in path。

假设我们想知道，是否存在一条权值至少为 W 的包围路径。这意味着，我们需要找到一条包围路径，它上面的所有点的点权 val(u) 都必须大于等于 W。

这启发我们，可以只使用那些点权 val(u) >= W 的点来构建我们的路径。一条包围路径（S-T 点割）存在，当且仅当在使用这些 val(u) >= W 的点构成的图中，S 和 T 是连通的。（如果 S 和 T 在这个子图中断开，那它们本来就是分开的，不需要我们去割；如果连通，我们总能找到一个割）。

所以问题转化为：对于一个查询点 u，找到最大的 W，满足：

1. val(u) >= W （因为 u 必须在路径上）。
2. 在由所有点权不小于 W 的非岛屿点构成的八连通图中，S 和 T 是连通的。

要对每个 W 都检查一次太慢了。这时候，Kruskal 重构树 就闪亮登场啦，喵！它可以一次性处理所有 W 的情况。

我们不直接在八连通图上建树，而是在四连通的非岛屿点图上建立。这是因为路径本身是四连通的。

1. 将所有非岛屿点，按照它们的点权 val 从大到小排序。
2. 初始化一个并查集，每个点自成一个集合。
3. 按顺序处理排序后的点 u。对于 u 的每个已经被处理过的四连通邻居 v，如果 u 和 v 不在同一个集合中，就在重构树中，将 v 所在集合的根节点作为 u 的子节点，然后合并这两个集合。u 的权值就是 val(u)。

这样建出的树（森林）就是 Kruskal 重构树。它有非常棒的性质：

• 它是一棵堆有序的树：父节点的 val 小于等于子节点的 val。
• 树上任意两点 a, b 的最近公共祖先（LCA）的 val，就是原图中 a 到 b 所有路径中，路径上点权最小值的最大值（即最大瓶颈路）。
• 一个节点 p 的子树中的所有叶子节点，构成了一个连通块，其中任意两点都可以通过点权不小于 val(p) 的路径互相到达。

第四步：离线查询与可撤销并查集

有了重构树，问题就变成了：对于每个查询点 u，我们需要找到它深度最浅（val 最小）的祖先 p，使得 p 的子树所代表的点集，能够在八连通图中连通 S 和 T。这个 val(p) 就是答案。

为什么是深度最浅的祖先呢？因为祖先越浅，val 越小，但其子树包含的点越多，越有可能连通 S 和 T。我们要找的是恰好能满足连通性的那个临界点，以得到最大的 W。

这引出了最终的核心问题：对重构树中的每个节点 p，判断其子树中的所有点，能否在八连通图中连通 S 和 T。

这是一个经典的离线问题，我们可以通过一次对重构树的 DFS 来解决所有节点的查询。为了在 DFS 的过程中动态维护图的连通性（添加节点、递归、再移除节点），我们需要使用可撤销并查集（DSU with Rollback）。

算法流程如下：

1. 在重构树上进行一次 DFS，我们称之为 solve(p)。
2. 进入 solve(p) 时，记录当前可撤销并查集的状态。
3. 将节点 p 自己所代表的那个原始点加入到八连通图中。具体操作是，检查它的八个邻居，如果邻居是边界，就与 S 合并；如果是岛屿，就与 T 合并；如果是其他已在图中（即 p 的祖先）的非岛屿点，就与那个点合并。所有合并操作都记录下来。
4. 在当前状态下，检查 S 和 T 是否连通。如果连通，我们就记录下来：p 是一个“有效的”包围点集提供者。
5. 对 p 的所有孩子 c，递归调用 solve(c)。
6. 从所有递归调用返回后，撤销在第 3 步中对并查集所做的所有修改，恢复到进入 solve(p) 时的状态。

完成这次 DFS 后，我们就知道了每个节点 p 是否“有效”。

第五步：得到最终答案

最后一步~ 对于一个查询点 u，我们要找它深度最浅的有效祖先。我们可以再进行一次 DFS 来传递这个信息。 设 ans_provider[u] 为 u 深度最浅的有效祖先。 ans_provider[p] = is_valid[p] ? p : ans_provider[parent[p]] 这个递推关系可以在一次自顶向下的 DFS 中轻松完成。

预处理完所有点的 ans_provider 后，对于每个查询 (r, c)，其对应的节点为 u，答案就是 val(ans_provider[u])！

总结一下，我们的爪印🐾遍布了： 多源BFS -> Kruskal重构树 -> 可撤销并查集 + 离线DFS -> 答案统计DFS。 一整套组合拳下来，问题就解决啦！是不是很有趣，喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码哦！加了很多注释，希望能帮助主人理解，喵~

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <numeric>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 505;
const int MAX_NODES = MAXN * MAXN;

// --- 基本定义 ---
int n, m, q;
char grid[MAXN][MAXN];
int val[MAX_NODES]; // 点权：到最近火山的曼哈顿距离
int node_id(int r, int c) { return (r - 1) * m + c; }
pair<int, int> node_coords(int id) {
    return {(id - 1) / m + 1, (id - 1) % m + 1};
}

// --- 可撤销并查集 ---
struct DSU_Rollback {
    vector<int> parent;
    vector<pair<int, int>> history; // 记录(被修改位置, 旧值)

    DSU_Rollback(int size) : parent(size + 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int i) {
        while (parent[i] != i) i = parent[i];
        return i;
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            history.push_back({root_j, parent[root_j]});
            parent[root_j] = root_i;
        }
    }

    int current_version() { return history.size(); }

    void rollback(int version) {
        while (history.size() > version) {
            auto [pos, old_val] = history.back();
            history.pop_back();
            parent[pos] = old_val;
        }
    }
};

// --- Kruskal重构树相关 ---
struct NodeInfo {
    int id;
    int value;
    bool operator>(const NodeInfo& other) const {
        return value > other.value;
    }
};
int dsu_kruskal[MAX_NODES];
int find_kruskal(int i) {
    return dsu_kruskal[i] == i ? i : dsu_kruskal[i] = find_kruskal(dsu_kruskal[i]);
}
void unite_kruskal(int i, int j) {
    int root_i = find_kruskal(i);
    int root_j = find_kruskal(j);
    if (root_i != root_j) dsu_kruskal[root_j] = root_i;
}

vector<int> recon_tree[MAX_NODES];
int recon_parent[MAX_NODES];
bool is_valid_provider[MAX_NODES];
int final_ans_provider[MAX_NODES];

// --- 坐标方向 ---
int dr4[] = {-1, 1, 0, 0};
int dc4[] = {0, 0, -1, 1};
int dr8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

void solve() {
    cin >> n >> m >> q;
    int total_nodes = n * m;

    // --- 初始化 ---
    vector<NodeInfo> non_island_nodes;
    queue<pair<int, int>> q_bfs;
    for (int i = 1; i <= total_nodes; ++i) {
        val[i] = INF;
        recon_tree[i].clear();
        recon_parent[i] = 0;
        is_valid_provider[i] = false;
        dsu_kruskal[i] = i;
    }

    // --- 1. 预处理点权 (多源BFS) ---
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'v') {
                q_bfs.push({i, j});
                val[node_id(i, j)] = 0;
            }
            if (grid[i][j] != '#') {
                non_island_nodes.push_back({node_id(i, j), 0});
            }
        }
    }

    while (!q_bfs.empty()) {
        auto [r, c] = q_bfs.front();
        q_bfs.pop();
        int u = node_id(r, c);
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr4[i];
            int nc = c + dc4[i];
            if (nr >= 1 && nr <= n && nc >= 1 && nc <= m) {
                int v = node_id(nr, nc);
                if (val[v] > val[u] + 1) {
                    val[v] = val[u] + 1;
                    q_bfs.push({nr, nc});
                }
            }
        }
    }
    
    for (auto& node : non_island_nodes) {
        node.value = val[node.id];
    }

    // --- 2. Kruskal重构树 ---
    sort(non_island_nodes.begin(), non_island_nodes.end(), greater<NodeInfo>());
    vector<bool> processed(total_nodes + 1, false);

    for (const auto& node : non_island_nodes) {
        int u = node.id;
        processed[u] = true;
        auto [r, c] = node_coords(u);
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr4[i];
            int nc = c + dc4[i];
            if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && grid[nr][nc] != '#') {
                int v = node_id(nr, nc);
                if (processed[v] && find_kruskal(u) != find_kruskal(v)) {
                    int root_v = find_kruskal(v);
                    recon_tree[u].push_back(root_v);
                    recon_parent[root_v] = u;
                    unite_kruskal(u, v);
                }
            }
        }
    }

    // --- 3. 离线检查连通性 (DFS + 可撤销并查集) ---
    int S = total_nodes + 1, T = total_nodes + 2;
    DSU_Rollback dsu_conn(total_nodes + 2);
    vector<bool> active_nodes(total_nodes + 1, false);

    function<void(int)> check_connectivity_dfs = 
        [&](int u) {
        int version = dsu_conn.current_version();
        active_nodes[u] = true;

        auto [r, c] = node_coords(u);
        for (int i = 0; i < 8; ++i) {
            int nr = r + dr8[i];
            int nc = c + dc8[i];
            if (nr < 1 || nr > n || nc < 1 || nc > m) { // 边界
                dsu_conn.unite(u, S);
                continue;
            }
            int v = node_id(nr, nc);
            if (grid[nr][nc] == '#') { // 岛屿
                dsu_conn.unite(u, T);
            } else if (active_nodes[v]) { // 已激活的邻居
                dsu_conn.unite(u, v);
            }
        }

        if (dsu_conn.find(S) == dsu_conn.find(T)) {
            is_valid_provider[u] = true;
        }

        for (int child : recon_tree[u]) {
            check_connectivity_dfs(child);
        }

        active_nodes[u] = false;
        dsu_conn.rollback(version);
    };

    for (const auto& node : non_island_nodes) {
        if (recon_parent[node.id] == 0) { // 是森林中的一棵树的根
            check_connectivity_dfs(node.id);
        }
    }

    // --- 4. 统计最终答案 ---
    function<void(int, int)> compute_final_ans_dfs = 
        [&](int u, int provider_p) {
        if (is_valid_provider[u]) {
            provider_p = u;
        }
        final_ans_provider[u] = provider_p;
        for (int child : recon_tree[u]) {
            compute_final_ans_dfs(child, provider_p);
        }
    };
    
    for (const auto& node : non_island_nodes) {
        if (recon_parent[node.id] == 0) {
            compute_final_ans_dfs(node.id, 0);
        }
    }

    // --- 5. 回答查询 ---
    while (q--) {
        int r, c;
        cin >> r >> c;
        int u = node_id(r, c);
        int provider_id = final_ans_provider[u];
        if (provider_id == 0) { // 理论上不会发生，因为保证有解
            cout << 0 << "\n";
        } else {
            cout << val[provider_id] << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

• 时间复杂度:

  1. 多源BFS预处理点权：每个点和边最多访问一次，复杂度为 $O(N \times M)$。
  2. Kruskal重构树：主要开销在于对所有非岛屿点（最多 $N \times M$ 个）进行排序，复杂度为 $O(NM \log(NM))$。之后建树的过程，每个点处理一次，并查集操作近乎常数，总共是 $O(NM \cdot \alpha(NM))$。
  3. 离线检查连通性：对重构树进行一次DFS，节点数为 $O(NM)$。在每个节点，我们检查8个邻居，并执行常数次可撤销并查集操作。并查集操作的复杂度为 $O(\log(NM))$。所以这部分总复杂度为 $O(NM \log(NM))$。
  4. 统计答案：一次DFS，复杂度为 $O(NM)$。

  综上，总的时间复杂度被排序和离线DFS主导，为 $O(NM \log(NM))$，非常高效，喵~

• 空间复杂度: 我们需要存储地图、点权数组、重构树的邻接表、并查集等。这些数据结构的大小都与地图大小 $N \times M$ 成正比。所以空间复杂度是 $O(N \times M)$。

知识点总结

这道题是一个非常好的综合题，把好几个高级算法思想巧妙地结合在了一起，像一盘精致的猫饭，喵~

1. 问题转化: 能够将“最大化最小值”问题与最大瓶颈路联系起来，并将“包围”抽象为图论中的S-T割，是解题的第一步。
2. Kruskal重构树: 它是解决最大瓶颈路、查询特定阈值下连通性的强大工具。通过按权值排序并用并查集合并，将一个图的连通性信息压缩到一棵树的结构中，非常优雅。
3. 离线思想: 当查询之间有关联（如此处的子树查询），或者可以被预先处理时，离线算法往往能大大优化复杂度。这里我们将所有节点的连通性查询通过一次DFS全部搞定。
4. 可撤销并查集: 这是处理需要“撤销”操作的动态图连通性问题的标准工具。在DFS中，进入子问题时修改数据结构，退出时恢复原状，可撤销并查集是完美的选择。

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问本喵，喵~ 加油！