题解：动态集合图最小边权查询

算法思路

本题需要维护一个动态图，支持点的集合移动和跨集合最小边权查询。由于数据规模大，采用度数分块的方法平衡复杂度。

1. 关键观察

• 操作涉及频繁的集合移动和最小边权查询
• 直接遍历所有边会超时，需要分类管理边
• 利用点的度数进行分块：度数大的为关键点，度数小的为普通点

2. 度数分块策略

设分块阈值 $MID = \sqrt{2m}$

• 关键点：度数 $\geq MID$ 的点，数量不超过 $O(\sqrt{m})$
• 普通点：度数 $< MID$ 的点

3. 数据结构设计

对于普通点-普通点的边：

• 使用 f[x][y]：存储集合 $(x,y)$ 之间所有边的权值（有序集合）
• 快速查询最小权值

对于关键点相关的边：

• 使用 crit[i][y]：存储关键点 $i$ 到集合 $y$ 的所有边权值
• 每个关键点维护到各集合的最小边权

4. 操作实现

Move 操作：

1. 普通点移动：
   • 更新与关键点连接的边：修改 crit
   • 更新与普通点连接的边：修改 f
2. 关键点移动：
   • 更新与其他关键点连接的边
   • 更新所在集合信息 P

Query 操作：

1. 检查普通点之间的边：f[x][y].begin()
2. 检查关键点与集合的边：遍历关键点查询 crit

代码实现

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

constexpr int _N = 5e5 + 5, _SN = 2e3 + 5, inf = 1e9;
int n, m, q;
int X[_N], Y[_N], W[_N];
int deg[_N], MID;
set<int> f[5][5], crit[_SN][5], P[5];
int id[_N];
vector<pair<int, int>> edge[_N];
unordered_map<int, int> num;
int cnt = 0;

// 判断是否为关键点
inline bool IsCri(int x) {
    return deg[x] >= MID;
}

// 移动点到目标集合
void Move(int x, int tar) {
    if (!IsCri(x)) { // 普通点
        // 更新与关键点连接的边
        for (auto e : edge[x]) {
            int v = e.first, w = e.second;
            if (IsCri(v)) {
                crit[num[v]][id[x]].erase(w);
                crit[num[v]][tar].emplace(w);
            }
        }
        
        // 更新与普通点连接的边
        for (auto e : edge[x]) {
            int v = e.first, w = e.second;
            if (!IsCri(v)) {
                int tx = min(id[x], id[v]), ty = max(id[x], id[v]);
                int fx = min(tar, id[v]), fy = max(tar, id[v]);
                f[tx][ty].erase(w);
                f[fx][fy].emplace(w);
            }
        }
        
        id[x] = tar;
    } else { // 关键点
        // 更新与其他关键点连接的边
        for (auto e : edge[x]) {
            int v = e.first, w = e.second;
            if (!IsCri(v)) continue;
            crit[num[v]][id[x]].erase(w);
            crit[num[v]][tar].emplace(w);
        }
        
        // 更新集合信息
        P[id[x]].erase(x);
        id[x] = tar;
        P[tar].emplace(x);
    }
}

// 查询两个集合之间的最小边权
int Query(int x, int y) {
    int res = !f[x][y].empty() ? *f[x][y].begin() : inf;
    
    // 检查关键点与集合y的边
    if (!P[x].empty()) {
        for (int u : P[x]) {
            if (crit[num[u]][y].empty()) continue;
            res = min(res, *crit[num[u]][y].begin());
        }
    }
    
    // 检查关键点与集合x的边  
    if (!P[y].empty()) {
        for (int u : P[y]) {
            if (crit[num[u]][x].empty()) continue;
            res = min(res, *crit[num[u]][x].begin());
        }
    }
    
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 读入图数据
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> X[i] >> Y[i] >> W[i];
        ++deg[X[i]], ++deg[Y[i]];
        edge[X[i]].emplace_back(Y[i], W[i]);
        edge[Y[i]].emplace_back(X[i], W[i]);
    }
    
    // 计算分块阈值
    MID = sqrt(2 * m);
    
    // 预处理关键点
    for (int i = 1; i <= n; ++i) {
        // 将关键点相关的边放在前面
        sort(edge[i].begin(), edge[i].end(), [](const auto &A, const auto &B) {
            return IsCri(A.first) > IsCri(B.first);
        });
        
        if (IsCri(i))
            num[i] = ++cnt;
    }
    
    // 初始化所有点在集合A
    for (int i = 1; i <= n; ++i)
        Move(i, 1);
    
    // 处理查询
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        string opt;
        cin >> opt;
        
        if (opt[0] == 'M') { // Move操作
            int x;
            cin >> x;
            int target = opt[5] - 'A' + 1;
            Move(x, target);
        } else { // Ask操作
            int set1 = opt[3] - 'A' + 1;
            int set2 = opt[4] - 'A' + 1;
            int ans = Query(set1, set2);
            
            if (ans != inf)
                cout << ans << '\n';
            else
                cout << "No Found!" << '\n';
        }
    }
    
    return 0;
}

关键优化

1. 度数分块

• 关键点：度数大，数量少，专门维护
• 普通点：度数小，直接维护边集

2. 边分类存储

• 普通点-普通点：f[][]
• 关键点-任意点：crit[][]

3. 操作复杂度

• Move操作：$O(\sqrt{m})$
• Query操作：$O(\sqrt{m})$

复杂度分析

• 预处理：$O(m \log m)$
• Move操作：$O(\sqrt{m} \log m)$
• Query操作：$O(\sqrt{m})$
• 总复杂度：$O(q\sqrt{m} \log m)$

对于 $n \leq 10^5, m \leq 5\times 10^5, q \leq 10^5$ 的数据规模，该算法能够高效运行。

这种度数分块的方法巧妙地将图操作问题转化为分类管理问题，是处理大规模动态图问题的有效技巧。