Road Reform

发表于 分类于 ，

    给出一个n个节点的图，以及m条无向有权边。m>=n

    还有一个数k。

    你可以删除一些边使得图成为一颗树。

    求在所有生成树中，满足树中边权最大值为k的最少操作。每次操作可以让一条边的边权值+1或-1。

Road Reform

Created by LXC on Sat Oct 14 02:41:56 2023

https://codeforces.com/problemset/problem/1468/J

ranting: 1800

tag: dsu, graphs, greedy

problem

给出一个n个节点的图，以及m条无向有权边。m>=n

还有一个数k。

你可以删除一些边使得图成为一颗树。

求在所有生成树中，满足树中边权最大值为k的最少操作。每次操作可以让一条边的边权值+1或-1。

solution

将边分为两类，第一类是权值大于k，第二类是权值小于等于k。

如果第二类边无法形成一颗生成树，那么需要添加第一类边。当添加第一类边后，只需将添加的边权全部修改为k就行，为了操作次数最小，优先选择边权较小的。为了保证构成生成树，我们需要并查集判断是否成环。

如果第二类边可以形成一颗生成树。对于这个由第二类边构成的生成树，只需要让其最大边变为k就行。所以我们需要优先选择权值较大的第二类边。此外我们可以将其中一条边替换为最小的一条第一类边。所以这种情况答案就是，所有边权中k-小于等于k的最大值和大于k的最小值-k二者的最小值。

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
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

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

struct Seg {
    int u, v, s;
    Seg(int u, int v, int s):u(u), v(v), s(s) {}
    bool operator<(const Seg& o) const {
        return s < o.s;
    }
};



void sol() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> st(n, -1);
    function<int(int)> ufind = [&](int x) {
        return st[x] < 0 ? x : st[x] = ufind(st[x]);
    };
    vector<Seg> seg;
    for (int i=0; i<m; i++) {
        int x, y, s;
        cin >> x >> y >> s;
        x--; y--;
        seg.emplace_back(x, y, s);
    }
    sort(seg.begin(), seg.end());
    ll mx = -1;
    for (int i=m-1; i>=0; i--) {
        if (seg[i].s <= k) {
            mx = max(1LL*seg[i].s , mx);
            int x = ufind(seg[i].u);
            int y = ufind(seg[i].v);
            if (x != y) {
                st[x] += st[y];
                st[y] = x;
            }
        }
    }

    

    if (-st[ufind(1)] != n) { // 小于等于k的边无法构成生成树。加边直到构成生成树。
        ll cnt = 0;
        for (int i=0; i<m; i++) {
            if (seg[i].s > k) {
                int x = ufind(seg[i].u);
                int y = ufind(seg[i].v);
                if (x != y) {
                    st[x] += st[y];
                    st[y] = x;
                    cnt += seg[i].s-k; // 所有大于k的边变为k，需操作次数
                }
                if (-st[ufind(1)] == n) { // 连通
                    break;
                }
            }
        }
        cout << cnt << "\n";
    } else { // 可以构成生成树，则k-mx为贡献，此外考虑替换一条边为 最小大于k的边
        ll cnt = 0x3f3f3f3f;
        for (int i=0; i<m; i++) {
            if (seg[i].s > k) {
                cnt = seg[i].s-k;
                break;
            }
        }
        cout << min(cnt, k-mx) << "\n";
    }

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}