DDOSvoid's Blog

CF 1633E Spanning Tree Queries

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/contest/1633/problem/E

简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，现在有 $k$ 次询问，每次询问给定一个常数 $x$，求如果将边权改为 $|w-x|$，$w$ 为改之前的边权，求最小生成树

$n\le 50,m\le 300,k\le 10^7$

Solution

对于求最小生成树，我们优先考虑 $kruskal$ 算法，另外注意到询问非常多，我们考虑离线处理

注意到如果我们使用 $kruskal$ 的话，那么我们只需要关注所有边的边权的相对关系，注意到只有当 $x$ 为 $\lceil\frac{w_i+w_j}{2}\rceil$ 时，$w_i$ 和 $w_j$ 这两条边的位置会发生变化，那么容易得到只有 $O(m^2)$ 种顺序，且每种顺序的 $x$ 都是一个区间

然后我们考虑如何处理询问，我们离线后对于每种顺序的左端点为 $x$ 将边排序后做 $kruskal$ 即可，记录选中的边原本的权值是否大于 $x$，然后就可以求出答案

有几个需要注意的地方，分界点除了 $\lceil\frac{w_i+w_j}{2}\rceil$ 以外，还要加入每种边的权值，这样可以防止边原本的权值和 $x$ 的大小关系发生变化，另外排序过程中第二关键字要按照边原本权值降序排序，保证答案尽量小

时间复杂度 $O(m^3\log m+k\log m^2)$

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 51
#define maxm 310
#define maxq 10000010
#define INF 1000000000
#define ll long long
using namespace std;

int n, m, p, k, a, b, c;
int t[maxm * maxm], cnt;
int Q[maxq];

struct Edge {
    int fr, to, w, c, id;

    friend bool operator < (const Edge &u, const Edge &v) {
        if (u.w == v.w) return u.c > v.c;
        return u.w < v.w;
    } 
} e[maxm];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

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

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> e[i].fr >> e[i].to >> e[i].c;
    t[cnt = 1] = 0; 
    for (int i = 1; i <= m; ++i)
        for (int j = i; j <= m; ++j) t[++cnt] = (e[i].c + e[j].c + 1) / 2;
    sort(t + 1, t + cnt + 1); cnt = unique(t + 1, t + cnt + 1) - t - 1; 
    cin >> p >> k >> a >> b >> c; ll ans = 0;
    for (int i = 1, x; i <= k; ++i) {
        if (i <= p) cin >> x;
        else x = (1ll * x * a + b) % c;
        Q[i] = x; 
    } sort(Q + 1, Q + k + 1); t[cnt + 1] = INF;
    for (int i = 1, j = 1; i <= cnt; ++i) {
        for (int k = 1; k <= m; ++k) e[k].w = abs(e[k].c - t[i]);
        sort(e + 1, e + m + 1); ll mst = 0, coef = 0; init_fa(n); 
        for (int k = 1; k <= m; ++k) {
            int u = e[k].fr, v = e[k].to, w = e[k].w, c = e[k].c, fu, fv;
            if ((fu = find(u)) == (fv = find(v))) continue; fa[fu] = fv;
            mst += w; coef += c <= t[i] ? 1 : -1;
        }
        while (j <= k && Q[j] >= t[i] && Q[j] < t[i + 1]) 
            ans ^= mst + coef * (Q[j++] - t[i]);
    } cout << ans << "\n";
    return 0;
}