图(Graph)的相关应用

连通图

题目链接：https://ac.nowcoder.com/acm/contest/86373/E

题意

    有一张$n$个点$m$条边组成的无向图，每个节点的权值为$a_i$;现在通过加边将这个图连成连通图，每次连边的代价是新形成的连通块的 最大元素值 ，请问 连通整张图 的最小代价是多少？

数据范围

  • $1 \le n \le 10^5,0 \le m \le 10^5$
题解

    从贪心的考虑出发，我们连通图的时候希望代价最小，那么各个连通块应该尽量选择小的连接，不难想到，若起始是$n$个孤立的点进行连接，那么只需要对权值进行 升序排序 ，最终的答案应该是$\sum\limits_{i=2}^{n} w_i$.
    回到本题，原始给定的这几条边，我们通过建图可以将连通的边分别统计出最大值，以此缩成一个点，再通过无向图遍历或者并查集维护最大值的方式得到各个连通图的最大权值，将这些点与孤立的点放入一个vector内进行排序，最终遍历求解.
    PS:题中所给的边不一定只构成一个连通图 ！！！

Code: 
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
#include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    vector<bool> vis(n + 1);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    while (m--){
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    i64 ans = 0;
    int mx = 0;
    auto dfs = [&](auto dfs, int u, int fa) -> void
    {
        if (vis[u])
            return;
        vis[u] = 1;
        mx = max(mx, a[u]); //维护最大元素值
        for (auto it : e[u]){ //无向图遍历
            if (it == fa)
                continue;
            dfs(dfs, it, u);
        }
    };
    vector<int> v;
    for (int i = 1; i <= n; i++){
        mx = 0;
        if (!vis[i]){
            if(e[i].size()) //已经存在边
                dfs(dfs, i, 0);
            else
                mx = a[i];
            v.emplace_back(mx); 
        }
    }
    sort(v.begin(), v.end()); //按权值大小升序
    int num = v.size();
    for (int i = 1; i < num; i++)
        ans += v[i];
    cout << ans << endl;
    return 0;
}

树(tree)的相关应用

树上操作

题目链接：https://codeforces.com/gym/104385/problem/I

题意

    有一棵$n$个节点的树，每条边的值为$w_i$,现在有$q$次操作，操作有两种类型：

  • $1 \: x \: y \: z$ 表示更改$x$和$y$之间的简单路径的每条边的值，将每条边的值异或上$z$,即$w \rightarrow w \oplus z$.
  • $2 \: d\:$输出连接到$d$节点的所有边的权值异或和.

数据范围

  • $1 \le n,q \le 5 \times 10^5$
  • $1 \le x,y \le n,0 \le w < 2^{20}$
  • $1 \le op \le 2$
  • $1 \le x,y \le n,0 \le z < 2^{20}$
  • $1 \le d \le n$
题解

    时间复杂度：$O(n+q)$
    本题输出的结果是所有 相邻边的异或和，显然不能通过枚举的方式求解，我们应该从始至终保存异或和的形式存储。
    设$ans[x]$为第x节点相邻边的异或和，通过一遍仅$O(n)$的DFS遍历便能轻松得到起始所有点的异或值。此时思考1操作对各个点的影响，不难想到，对于从$x \rightarrow y$的各点中，非端点恰有两条路径上的权值异或上$z$，根据XOR的性质可知，$z \oplus z=0$,所以非端点的异或和保持不变，只有端点的值会发生改变($w \rightarrow w \oplus z$).

Code: 
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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> ans(n + 1); //w权值最大仅为2^20,所以异或最大值也是2^20
    vector<vector<pair<int,int>> e(n + 1);
    for (int i = 1; i < n;i++){
        int a, b, w;
        cin >> a >> b >> w;
        e[a].emplace_back(b,w);
        e[b].emplace_back(a,w);
    }
    auto dfs = [&](auto dfs, int u, int fa) -> void {
        for(auto it:e[u])
            if(it.first != fa){
                //获取初始各点的异或和
                ans[u] ^= it.second, ans[it.first] ^= it.second;
                dfs(dfs, it.first, u);
            }
    };
    dfs(dfs, 1, 0);
    while(q--){
        int opt, x, y, z;
        cin >> opt;
        if(opt==1){
            cin >> x >> y >> z;
            ans[x] ^= z, ans[y] ^= z; //端点值改变
        }else{
            cin >> x;
            cout << ans[x] << endl;
        }
    }
    return 0;
}