Moe's CF Life

Appearance

F. Vicky's Delivery Service - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 561 (Div. 2) 标签: data structures, dsu, graphs, hashing 难度: *2400

嘿，主人！来看Vicky的魔法快递喵~ ​

Myaa~ 主人 sama，欢迎来到 Vicky 的魔法世界！这个世界里有好多城市和五颜六色的魔法道路。我们的主角 Vicky 小女巫需要完成一些快递任务，但她有个小小的限制：她只能走一种叫做“双重彩虹”的神奇路径！

那么，什么是“双重彩虹”路径呢？(ฅ'ω'ฅ) 一条从 c_1 到 c_k 的路径 c_1, c_2, ..., c_k 被称为双重彩虹，需要满足一个条件： 对于路径上的一连串 ... -> c_{2i-1} -> c_{2i} -> c_{2i+1} -> ... 这样的三元组，中间的两条路 (c_{2i-1}, c_{2i}) 和 (c_{2i}, c_{2i+1}) 颜色必须相同！

举个例子喵：A -> B -> C -> D -> E

  • A -> B -> C 这部分，A-B 和 B-C 的路颜色得一样。
  • C -> D -> E 这部分，C-D 和 D-E 的路颜色也得一样。

整个任务就是，会不断有新的路出现，Vicky 也会接到新的快递订单。我们要帮她判断，每个订单（从城市 u 到城市 v）能不能通过“双重彩虹”路径完成。

解题思路喵~ 魔法枢纽与并查集！ ​

一看到这种动态的连通性问题，猫猫的DNA就动了喵！这不就是并查集（DSU）的拿手好戏嘛~ 但是，这个“双重彩虹”的连接条件有点特别，我们不能直接把相连的城市合并。

我们需要换个角度思考。A 能通过颜色为 z 的路到达 B，B 又能通过颜色为 z 的路到达 C，于是 A 和 C 之间就建立了一种特殊的连接关系。我们可以把这个 B 点看作一个使用颜色 z 的“魔法中转站”。

于是，一个绝妙的想法诞生了！我们来创造一些虚拟节点！ 对于每个城市 u 和每种颜色 c，我们都可以定义一个虚拟节点，叫做“颜色枢纽 (Color Hub)”，记作 hub(u, c)。这个枢纽代表了“通过城市 u 进行颜色 c 的中转”的能力。

现在，当一条颜色为 z 的路连接了城市 u 和 v 时，会发生什么呢？

  1. 城市 u 可以通过这条路到达 v。在 v 这里，它好像接触到了一个颜色为 z 的中转站，所以我们可以认为 u 和 hub(v, z) 是连通的。
  2. 同理，城市 v 也连接到了 hub(u, z)。

所以，每增加一条边 (u, v, z)，我们就执行两次合并操作：

  • unite(u, hub(v, z))
  • unite(v, hub(u, z))

这样一来，如果 A 和 C 都能通过颜色为 z 的路连接到 B，那么：

  • unite(A, hub(B, z))
  • unite(C, hub(B, z))A 和 C 就都和 hub(B, z) 在同一个并查集里了，也就是说 find(A) == find(C)。它们之间就实现了“双重彩虹”式的连通！我们把这种连通叫做“DR-连通”（Double Rainbow-connected）好了喵~

但是，题目中的路径不一定完全由这种 A->B->C 的结构组成。比如 A->B 这样一条边本身就是一条合法的路径。再比如 A->B->C->D，其中 A-B 和 B-C 颜色相同，但 C-D 的颜色可能不同。

这说明，从 u 到 v 的一条完整路径，可以看作是：

  1. u 和 v 本身就是 DR-连通的。
  2. 或者，u 先通过 DR-连通的方式到达某个城市 u'，然后 u' 和 v 之间恰好有一条普通的道路直接相连。

这给了我们最终的查询策略： 对于查询 ? u v：

  1. 检查 u 和 v 是否 DR-连通，即 find(u) == find(v)。如果是，那么 "Yes"！
  2. 如果不是，我们就需要检查 u 所在的整个 DR-连通块中，是否有任何一个城市 u' 和 v 有直接的边相连。

为了高效地实现第二点，我们可以在并查集的每个根节点上，额外维护一个 std::set，用来存储这个连通块内所有城市能够通过单条边直达的所有邻居城市。当合并两个集合时，我们使用**启发式合并（按大小合并）**来合并这两个 set，以保证效率。

这样，我们的整个方案就完整啦！(๑•̀ㅂ•́)و✧

代码实现喵~ ​

cpp
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <utility>
#include <algorithm>

// 定义我们的并查集结构喵~
struct DSU {
    std::vector<int> parent; // 记录每个节点的父节点
    std::vector<int> ds_size; // 记录每个集合的大小（用于按大小合并）
    std::vector<std::set<int>> adj; // 记录每个连通块的所有单边邻居！这是关键喵~
    int node_count; // DSU中总的节点数（包括城市和虚拟的hub节点）

    DSU() : node_count(0) {}

    // 初始化n个城市节点
    void init(int n) {
        node_count = n;
        parent.resize(node_count + 1);
        ds_size.resize(node_count + 1);
        adj.resize(node_count + 1);
        for (int i = 1; i <= node_count; ++i) {
            parent[i] = i;
            ds_size[i] = 1;
        }
    }

    // 查找根节点（带路径压缩）
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    // 合并两个集合
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // 按大小合并，小的合并到大的里面
            if (ds_size[root_i] < ds_size[root_j])
                std::swap(root_i, root_j);
            
            parent[root_j] = root_i;
            ds_size[root_i] += ds_size[root_j];
            
            // 启发式合并邻居集合！把小的set合并到大的里面，效率更高喵
            if (adj[root_i].size() < adj[root_j].size()) {
                std::swap(adj[root_i], adj[root_j]);
            }
            for (int neighbor : adj[root_j]) {
                adj[root_i].insert(neighbor);
            }
            adj[root_j].clear(); // 清空小的集合
        }
    }

    // 动态添加一个新节点（用于创建hub）
    int add_node() {
        node_count++;
        parent.push_back(node_count);
        ds_size.push_back(1);
        adj.emplace_back();
        return node_count;
    }
};

DSU dsu;
// 用一个map来给 (城市, 颜色) 这种hub组合一个独一无二的ID
std::map<std::pair<int, int>, int> hub_map;

// 获取或创建一个hub节点的ID
int get_hub(int city, int color) {
    auto it = hub_map.find({city, color});
    if (it == hub_map.end()) {
        int new_id = dsu.add_node();
        hub_map[{city, color}] = new_id;
        return new_id;
    }
    return it->second;
}

// 添加一条边的逻辑
void add_edge(int u, int v, int z) {
    // 记录合并前的根，用来更新邻居集合
    int root_u_before = dsu.find(u);
    int root_v_before = dsu.find(v);
    
    // 如果u和v不在同一个DR-连通块，那么它们之间的这条边就是新的单边连接
    if (root_u_before != root_v_before) {
        dsu.adj[root_u_before].insert(v);
        dsu.adj[root_v_before].insert(u);
    }
    
    // 获取两个方向的hub节点
    int hub_uz = get_hub(u, z);
    int hub_vz = get_hub(v, z);
    
    // 将城市和对应的hub合并，建立DR-连通关系
    dsu.unite(v, hub_uz);
    dsu.unite(u, hub_vz);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, c, q;
    std::cin >> n >> m >> c >> q;

    dsu.init(n);

    // 处理初始的m条边
    for (int i = 0; i < m; ++i) {
        int u, v, z;
        std::cin >> u >> v >> z;
        add_edge(u, v, z);
    }

    // 处理q个事件
    for (int i = 0; i < q; ++i) {
        char type;
        std::cin >> type;
        if (type == '+') {
            int u, v, z;
            std::cin >> u >> v >> z;
            add_edge(u, v, z);
        } else {
            int u, v;
            std::cin >> u >> v;
            int root_u = dsu.find(u);
            int root_v = dsu.find(v);
            
            // 条件1: u和v是否DR-连通？
            if (root_u == root_v) {
                std::cout << "Yes\n";
            } else {
                // 条件2: u的连通块中，是否有节点能单边直达v？
                if (dsu.adj[root_u].count(v)) {
                    std::cout << "Yes\n";
                } else {
                    std::cout << "No\n";
                }
            }
        }
    }

    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O((m+q) * log²(n+m+q)) 的说。

    • DSU中的元素总数最多是 n + 2*(m+q)，我们记为 N。
    • find 和 unite 的基本操作接近 O(α(N))，可以看作是常数。
    • 主要开销在于合并邻居集合 adj。我们用了启发式合并，一个元素每次被移动，其所在集合的大小至少翻倍，所以每个邻居关系最多被移动 O(log N) 次。
    • 每次移动需要向 std::set 中插入，耗时 O(log K)，其中 K 是 set 的大小。
    • 所以处理所有 m+q 条边的总时间复杂度是 O((m+q) * log N * log N)。
    • 查询操作 ? 的复杂度是 O(log n)，因为 set 的查询很快。
    • 总的来说，这个复杂度对于题目给定的数据范围是完全可以接受的，跑得飞快喵！

  • 空间复杂度: O(n + m + q) 的说。

    • DSU 的 parent 和 ds_size 数组大小为 O(N) = O(n+m+q)。
    • hub_map 最多存储 2*(m+q) 个条目。
    • adj 集合中存储的邻居关系总数也是 O(m+q)。
    • 所以总空间是线性的，很省内存的说~

知识点与总结喵！ ​

这道题真的太有趣了喵！它完美地展示了如何用创造性的建模来解决看似棘手的问题。

  1. 核心思想: 将特殊的路径规则（双重彩虹）转化为图论中的连通性问题。这是解决这类问题的通用思路。
  2. 关键技巧:
    • 虚拟节点/抽象建模: 引入“颜色枢纽 (Color Hub)”作为虚拟节点，是解题的钥匙！它巧妙地将“经过某点、使用某颜色”这个复杂的行为，变成了节点间的简单连接关系。
    • 带附加信息的并查集: 我们的并查集不光维护连通性，还在根节点上附加了一个 set，用来维护整个连通块的邻接信息。这让并查集的功能变得更加强大！
    • 启发式合并 (Small-to-large Merging): 在合并 set 这种数据结构时，始终将小的合并到大的里面，是保证复杂度的关键。这个技巧在很多题目中都有用武之地哦！

希望这篇题解能帮到主人理解这道题的奥妙！遇到难题不要怕，试着从不同角度思考，说不定就能发现像“魔法枢纽”这样可爱的解法呢！继续加油喵~ (´,,•ω•,,)♡

Released under the MIT License.

Copyright © 2024-present Moe