[蓝桥杯 2020 省 AB1] 网络分析

题意

初始时每个点单独成块。

有两种操作：

1 x y：把 x 和 y 连起来
2 x t：从 x 所在连通块发送一条大小为 t 的信息，这个连通块里的所有点都会存下这条信息

最后要求输出每个点一共存了多少信息。

样例可以按“当时属于哪个连通块”来理解：

操作	影响
`1 1 2`	连通块变成 `{1,2}`、`{3}`、`{4}`
`2 1 10`	`1,2` 都加 `10`
`2 3 5`	`3` 加 `5`
`1 4 1`	连通块变成 `{1,2,4}`、`{3}`
`2 2 2`	`1,2,4` 都加 `2`
`2 2 1`	`1,2,4` 都再加 `1`

所以最后是：

1 = 10 + 2 + 1 = 13
2 = 10 + 2 + 1 = 13
3 = 5
4 = 2 + 1 = 3

思路

先看一个直接按图模拟的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70// brute.cpp：直接维护原图，每次发送消息都 BFS 整个连通块。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n, m;
vector<int> graph[MAXN];
long long answer[MAXN];
bool vis[MAXN];

void add_edge(int x, int y) {
    graph[x].push_back(y);
    graph[y].push_back(x);
}

void spread_message(int start, int value) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));

    q.push(start);
    vis[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        answer[u] += value;

        for (int v : graph[u]) {
            if (vis[v]) {
                continue;
            }
            vis[v] = true;
            q.push(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        answer[i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            add_edge(x, y);
        } else {
            spread_message(x, y);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}

暴力做法很直接：

连边操作就真的往图里加边
发送消息操作就从 x 出发 BFS/DFS 一遍，把整个连通块都加上 t

这个做法容易理解，但每次发消息都扫整个连通块，操作多了会超时。

这题难点在于：同一个点，只有在它已经属于那个连通块的时候，才应该收到当时发送的消息。

所以不能在最后只看“最终属于哪个连通块”，而要保留“每次合并的历史”。

一个很自然的办法是建一棵并查集合并树：

开始时 1..n 这些原点都是叶子
每次 1 x y 真正把两个不同连通块合并时，就新建一个虚点 tot
让这个虚点成为这两个连通块的新父亲

这样，这个虚点的整棵子树，正好表示“从这一刻开始，已经连到一起的所有点”。

接下来处理消息操作：

遇到 2 x t 时，只给 x 当前所在连通块的根节点加一个 t
不立刻往下发

为什么可以这样做？

因为这个根节点的子树，恰好就是“这次消息应该覆盖到的所有原节点”。等所有操作结束后，再从每棵合并树的根往下 DFS：

路上的标记累加下来
到达某个原节点时，它拿到的累计值就是答案

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXV = 20005;

int n, m;
int tot;
int fa[MAXV];
int tree_parent[MAXV];
int left_child[MAXV], right_child[MAXV];
long long add_tag[MAXV];
long long answer[MAXN];

void init_dsu(int n) {
    tot = n;
    for (int i = 1; i < MAXV; i++) {
        fa[i] = i;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

// 有效合并时，新建一个虚点作为两个连通块的新根。
void merge_block(int x, int y) {
    int rx = find_root(x);
    int ry = find_root(y);

    if (rx == ry) {
        return;
    }

    ++tot;
    left_child[tot] = rx;
    right_child[tot] = ry;
    tree_parent[rx] = tot;
    tree_parent[ry] = tot;

    fa[rx] = tot;
    fa[ry] = tot;
    fa[tot] = tot;
}

void dfs(int u, long long sum) {
    sum += add_tag[u];

    if (u <= n) {
        answer[u] = sum;
        return;
    }

    if (left_child[u] != 0) {
        dfs(left_child[u], sum);
    }
    if (right_child[u] != 0) {
        dfs(right_child[u], sum);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init_dsu(n);

    for (int i = 1; i <= m; i++) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            merge_block(x, y);
        } else {
            int root = find_root(x);
            add_tag[root] += y;
        }
    }

    for (int i = 1; i <= tot; i++) {
        if (tree_parent[i] == 0) {
            dfs(i, 0);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}

复杂度

设点数为 $n$ ，操作数为 $m$ 。

并查集合并和查找总复杂度近似 $O(m \alpha(n))$
最后 DFS 一次合并树是 $O(n)$

总复杂度可以看成 $O(m \alpha(n) + n)$ 。

空间复杂度 $O(n)$ ，因为有效合并最多 $n-1$ 次，合并树总点数不超过 $2n-1$ 。

总结

这题最容易想错的地方，是把“给当前连通块发消息”误写成“给最终连通块发消息”。

一旦看出消息要绑定在“当时那个连通块”上，合并树就很自然了：合并时建父节点，发消息时给当前根打标记，最后统一下传。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[蓝桥杯 2020 省 AB1] 网络分析

目录

题意

思路

代码

复杂度

总结

一图流解析