雷光昊 @ 2025-12-8 16:12:26

「RMI 2018」Colors 题解

给定一个连通无向图 $G=(V,E)$ ， $|V|=N$ ， $|E|=M$ 。每个节点 $u$ 有一个初始颜色 $a_u$ 和目标颜色 $b_u$ ，颜色值在 $[1,N]$ 之间。

允许的操作：对于任意边 $(u,v) \in E$ ，可以执行 $a_u = \min(a_u, a_v)$ （即用邻居的最小值更新当前节点）。

问：是否可以通过一系列这样的操作，使得所有节点的颜色变为目标颜色 $b$ 。

关键性质分析

1. 操作的基本性质

单向性：操作 $a_u = \min(a_u, a_v)$ 只能减小 $a_u$ 或保持不变
传播性：最小值可以通过边在图中传播
必要条件：对于所有 $u$ ，必须有 $b_u \leq a_u$ （因为颜色只能减小）

2. 反向思考

从最终状态 $b$ 反向考虑：

最终颜色为 $c$ 的节点集合 $T_c = \{u \mid b_u = c\}$
初始颜色为 $c$ 的节点集合 $S_c = \{u \mid a_u = c\}$

对于颜色 $c$ ，要使 $T_c$ 中的所有节点最终成为颜色 $c$ ，必须满足：

$S_c$ 非空（否则无法产生颜色 $c$ ）
在子图 $G_c$ （由所有满足 $b_u \geq c$ 的节点组成）中， $T_c$ 的每个节点都能到达 $S_c$ 的某个节点

解决方案

算法框架

检查必要条件： $b_u \leq a_u$ 对所有 $u$
按颜色值从大到小处理： $c = N, N-1, \ldots, 1$
对于每个颜色 $c$ ：
- 如果 $T_c$ 非空但 $S_c$ 为空，则不可能
- 在当前子图 $G_c$ 中，检查 $T_c$ 的所有节点是否与 $S_c$ 的某个节点连通
- 从子图中移除所有 $b_u = c$ 的节点

数据结构设计

使用并查集维护连通性：

按颜色值从大到小处理
逐步"激活"节点（当 $b_u \geq c$ 时激活）
激活节点时，将其与已激活的邻居合并

详细算法步骤

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, size;
    
    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (size[x] < size[y]) swap(x, y);
        parent[y] = x;
        size[x] += size[y];
    }
};

bool solve(int n, vector<int>& a, vector<int>& b, vector<pair<int,int>>& edges) {
    // 步骤1：检查必要条件
    for (int i = 0; i < n; i++) {
        if (b[i] > a[i]) return false;
    }
    
    // 步骤2：按颜色分组
    vector<vector<int>> target_by_color(n+1);  // 目标颜色为c的节点
    vector<vector<int>> source_by_color(n+1);  // 初始颜色为c的节点
    
    for (int i = 0; i < n; i++) {
        target_by_color[b[i]].push_back(i);
        source_by_color[a[i]].push_back(i);
    }
    
    // 步骤3：构建邻接表
    vector<vector<int>> adj(n);
    for (auto& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 步骤4：并查集 + 从大到小处理颜色
    DSU dsu(n);
    vector<bool> active(n, false);  // 节点是否在当前子图中
    vector<int> component_root(n, -1);  // 每个连通分量的代表颜色源节点
    
    // 从大到小处理颜色
    for (int c = n; c >= 1; c--) {
        // 激活所有目标颜色为c的节点
        for (int u : target_by_color[c]) {
            active[u] = true;
            // 连接已激活的邻居
            for (int v : adj[u]) {
                if (active[v]) {
                    dsu.unite(u, v);
                }
            }
        }
        
        // 处理当前颜色c
        if (!target_by_color[c].empty()) {
            // 需要至少一个初始颜色为c的节点
            if (source_by_color[c].empty()) return false;
            
            // 找到所有初始颜色为c且已激活的节点
            vector<int> active_sources;
            for (int src : source_by_color[c]) {
                if (active[src]) {
                    active_sources.push_back(src);
                }
            }
            
            if (active_sources.empty()) {
                // 没有已激活的源节点，检查是否可能
                // 这种情况发生在：源节点的目标颜色 < c，所以它们之前就被移除了
                // 我们需要检查目标节点是否能连接到这些源节点
                // 实际上，如果源节点不活跃，意味着 b[src] < c
                // 但源节点的颜色是c，目标颜色 < c，这违反 b[src] ≤ a[src]?
                // 不，b[src] < c = a[src] 是允许的
                // 问题：源节点不在当前子图中，但目标节点需要连接到它们
                // 解决方案：我们需要在源节点活跃时（当处理颜色 b[src] 时）记录连通分量信息
            } else {
                // 有活跃的源节点，检查连通性
                int expected_root = dsu.find(active_sources[0]);
                for (int src : active_sources) {
                    if (dsu.find(src) != expected_root) {
                        // 源节点不在同一个连通分量
                        // 这不一定导致失败，只要每个目标节点能连接到某个源节点
                    }
                }
                
                // 检查所有目标节点
                for (int u : target_by_color[c]) {
                    bool connected = false;
                    for (int src : active_sources) {
                        if (dsu.find(u) == dsu.find(src)) {
                            connected = true;
                            break;
                        }
                    }
                    if (!connected) return false;
                }
            }
        }
        
        // 移除颜色为c的节点？实际上我们不需要显式移除，
        // 因为在下一次循环中，我们会处理更小的颜色
    }
    
    return true;
}

修正算法：记录连通分量信息

上面的算法有一个问题：当源节点不活跃时（ $b[src] < c$ ），我们无法检查连通性。

解决方案：在处理每个颜色 $c$ 时，不仅激活目标颜色为 $c$ 的节点，还要标记"好的"连通分量。

改进算法：

bool solve(int n, vector<int>& a, vector<int>& b, vector<pair<int,int>>& edges) {
    // 检查必要条件
    for (int i = 0; i < n; i++) {
        if (b[i] > a[i]) return false;
    }
    
    // 分组
    vector<vector<int>> target_by_color(n+1);
    vector<vector<int>> source_by_color(n+1);
    
    for (int i = 0; i < n; i++) {
        target_by_color[b[i]].push_back(i);
        source_by_color[a[i]].push_back(i);
    }
    
    // 构建图
    vector<vector<int>> adj(n);
    for (auto& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 并查集和标记数组
    DSU dsu(n);
    vector<bool> good(n, false);  // 连通分量是否"好"（包含合适的源节点）
    vector<bool> active(n, false);  // 节点是否已激活
    
    // 从大到小处理颜色
    for (int c = n; c >= 1; c--) {
        // 第一步：标记当前颜色的源节点为"好"
        for (int src : source_by_color[c]) {
            if (active[src]) {  // 如果源节点已激活
                good[dsu.find(src)] = true;
            }
        }
        
        // 第二步：激活目标颜色为c的节点
        for (int u : target_by_color[c]) {
            active[u] = true;
            // 连接已激活的邻居
            for (int v : adj[u]) {
                if (active[v]) {
                    int root_u = dsu.find(u);
                    int root_v = dsu.find(v);
                    if (root_u != root_v) {
                        // 合并连通分量，保留"好"的标记
                        dsu.unite(u, v);
                        int new_root = dsu.find(u);
                        good[new_root] = good[root_u] || good[root_v];
                    }
                }
            }
        }
        
        // 第三步：检查目标颜色为c的节点
        for (int u : target_by_color[c]) {
            if (!good[dsu.find(u)]) {
                return false;
            }
        }
        
        // 第四步：为下一轮准备，清除当前颜色的源节点标记
        // 实际上不需要清除，因为"好"标记是累积的
        // 但需要注意：源节点的颜色c应该只在处理≥c的颜色时有效
        // 修改：在处理完颜色c后，移除"好"标记中由颜色c源节点贡献的部分
        // 更简单的方法：在标记时为每个颜色存储标记
        
        // 实现：使用数组标记每个连通分量的最小可用颜色
        // 另一种思路：使用并查集维护每个连通分量的最小源颜色
    }
    
    return true;
}

最终优化算法

bool solve(int n, vector<int>& a, vector<int>& b, vector<pair<int,int>>& edges) {
    // 检查必要条件
    for (int i = 0; i < n; i++) {
        if (b[i] > a[i]) return false;
    }
    
    // 分组
    vector<vector<int>> target_by_color(n+1);
    vector<vector<int>> source_by_color(n+1);
    
    for (int i = 0; i < n; i++) {
        target_by_color[b[i]].push_back(i);
        if (a[i] >= b[i]) {  // 只有 a[i] ≥ b[i] 的源节点才可能有用
            source_by_color[a[i]].push_back(i);
        }
    }
    
    // 构建图
    vector<vector<int>> adj(n);
    for (auto& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 并查集
    DSU dsu(n);
    vector<bool> active(n, false);
    vector<int> min_source_color(n, 0);  // 每个连通分量的最小源颜色
    
    // 初始化：对于每个节点，如果有源颜色，设置min_source_color
    for (int i = 0; i < n; i++) {
        if (a[i] >= b[i]) {
            min_source_color[i] = a[i];
        }
    }
    
    // 从大到小处理颜色
    for (int c = n; c >= 1; c--) {
        // 激活目标颜色为c的节点并合并
        for (int u : target_by_color[c]) {
            active[u] = true;
            for (int v : adj[u]) {
                if (active[v]) {
                    int root_u = dsu.find(u);
                    int root_v = dsu.find(v);
                    if (root_u != root_v) {
                        dsu.unite(u, v);
                        int new_root = dsu.find(u);
                        // 合并时更新最小源颜色
                        min_source_color[new_root] = max(min_source_color[root_u], min_source_color[root_v]);
                    }
                }
            }
        }
        
        // 检查目标颜色为c的节点
        if (!target_by_color[c].empty()) {
            bool ok = false;
            for (int u : target_by_color[c]) {
                int root = dsu.find(u);
                if (min_source_color[root] >= c) {
                    ok = true;
                    break;
                }
            }
            if (!ok) return false;
        }
        
        // 注意：我们不需要显式移除节点
        // min_source_color 已经考虑了所有活跃节点的源颜色
    }
    
    return true;
}

复杂度分析

时间复杂度： $O(N + M \cdot \alpha(N))$ $O (N + M \cdot α (N))$
- 分组： $O(N)$
- 并查集操作： $O(M \cdot \alpha(N))$
- 按颜色处理： $O(N)$
空间复杂度： $O(N + M)$

算法正确性证明

必要性

如果可以通过操作从 $a$ 得到 $b$ ，则：

$b_u \leq a_u$ 对所有 $u$
对于每个颜色 $c$ ，所有最终颜色为 $c$ 的节点必须能从某个初始颜色为 $c$ 的节点通过路径到达，且路径上节点的最终颜色 $\geq c$

充分性

如果上述条件满足，我们可以构造操作序列：

从颜色值最大的节点开始
通过操作将最小值沿路径传播
逐步处理所有颜色

算法标签

图结构：连通性分析、图遍历
贪心：按颜色值从大到小处理
并查集：维护连通分量信息
必要条件判断： $b_u \leq a_u$

总结

本题的核心是将操作可行性问题转化为图的连通性问题：

关键观察：操作 $a_u = \min(a_u, a_v)$ 的本质是最小值在图上传播
算法框架：从目标状态反向思考，按颜色值从大到小检查连通性
数据结构：使用并查集高效维护连通分量和最小源颜色
优化：充分利用 $b_u \leq a_u$ 的条件，只考虑有用的源节点

该算法能在 $O(N+M)$ 时间内解决问题，满足题目的大数据量要求。

ID

5892

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

雷光昊

1 条题解