带权并查集解决P8710网络分析

「ゲームとOI」 · 2024-04-09 13:37:00 · 题解

题目大意

题目给定 n 个元素和 m 个操作，每次操作有两种情况：

• 2$ $a$ $t$ 将 $a$ 所在的集合的所有元素加 $t

解题思路

考虑采用并查集来做，首先想到发送数据操作时只对根操作来减少时间复杂度。

在这一前提下，我们只需在集合合并时维护两集合间关系即可，思考发现集合 A 和 集合 B 合并后，两集合内任意点差值不再改变，因此选取根节点之间差值作为并查集出边权重。

定义 root(x) 为 x 的根节点， val(x) 为 x 节点的空间占用值，w(x) 为 x 节点的出边权重。

对于任意节点 x，从x到根节点的路径节点集合为 P，则

路径压缩时,累计路径上权值计算出新的 val(x)，借此修改 w(x)。本质上是将路径上权重累计起来，作为新的权重，即

或者

代码实现

具体实现代码如下，时间复杂度与原始并查集算法相同，为 O(n)。

#include <iostream>
using namespace std;

int root[10005];
int val[10005];
int w[10005];

// 查找根节点
// p：当前节点
// value：引用形式回传累计得到的val(p)
// 返回值：根节点标号
int find(int p, int &value) {
    if(root[p] == p) {
        value = val[p];
        return p;
    }
    else {
        val[p] = 0; // 重置val重新计算（此时未计算本节点出边）
        root[p] = find(root[p], val[p]);    // 压缩路径
        value = (val[p] += w[p]);           // 更新上级累计值（计算本节点出边）
        w[p] = val[p] - val[root[p]];       //更新路径权重
        return root[p];
    }
}

// 获得p点val值
int value(int p) {
    find(p, val[p]);
    return val[p];
}

// 获得p点根节点
int top(int p) {
    find(p, val[p]);
    return root[p];
}

// 连接a与b两节点
void link(int a, int b) {
    a = top(a), b = top(b); // 转换为根节点连接
    root[b] = a;            // 连接节点
    w[b] = val[b] - val[a]; // 获得两根节点差值作为权重
}

// 对p点增加t值
void add(int p, int t) {
    p = top(p);
    val[p] += t;
}

int main(void) {
    int n, m, t, p, a;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) {
        root[i] = i, val[i] = w[i] = 0;
    }
    for(int i = 0;i < m;i ++) {
        cin >> a >> p >> t;
        if(a == 1) {
            link(p, t);
        }
        else {
            add(p, t);
        }
    }
    for(int i = 1;i <= n;i ++) {
        cout << value(i) << " ";
    }
    cout << endl;
    return 0;
}