题目描述

难度分:$1800$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$ 之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$，$m(n-1 \leq m \leq min(2 \times 10^5,\frac{n \times (n-1)}{2})$，$k(1 \leq k \leq 10^9)$，表示一个$n$点$m$边的无向图。

然后输入$m$条边，每条边输入$x$，$y$，$w(1 \leq w \leq 10^9)$，表示有一条边权为$w$的无向边连接$x$和$y$。节点编号从$1$开始。保证图是连通的。保证图中无自环和重边。

首先，求出图的一棵生成树。然后，每次操作，可以把生成树的一条边的边权加一或者减一。要使生成树的最大边权恰好等于$k$，最少要操作多少次？

输入样例

4
4 5 7
4 1 3
1 2 5
2 3 8
2 4 1
3 4 4
4 6 5
1 2 1
1 3 1
1 4 2
2 4 1
4 3 1
3 2 1
3 2 10
1 2 8
1 3 10
5 5 15
1 2 17
3 1 15
2 3 10
1 4 14
2 5 8

输出样例

1
3
0
0

算法

二分答案+$Kruskal$算法

分为以下两种情况进行讨论：

一、如果生成树的最大边权是大于等于$k$的

此时小于$k$的边权不需要动，我们只需要把大于$k$的边权都减成$k$就行了，这时候要想减一的操作数小，就要求最大的那条边权尽可能接近$k$（即在大于$k$的前提下越小越好，最大值最小化问题）。最小化最大值就很容易想到二分答案，我们可以对边集按照边集升序排列，找到第一个权值不小于$k$的边$l$，令$r=m-1$，在$[l,r]$上二分答案。对于一个给定的$mid$，先将这条边的两个端点合并，然后在权值小于它的边上运行$Kruskal$算法（二分$check$函数的逻辑）：

1. 如果能够使得图连通，说明保留$mid$边的权值是合法的，记录答案并往左搜索看能不能更小。
2. 否则$mid$边的权值太小了，还需要囊括权值更大的边才能形成生成树，往右搜索。

只要在这种情况下有解，我们得到的最大边权是$index$的权值，就在边集$[0,index]$上再运行一遍$Kruskal$算法，在边权$w \gt k$时把$w-k$累加到答案上即可。

二、如果生成树的最大边权是小于$k$的

此时我们只要把最大的这一条边利用加一操作加到$k$就可以了。这时候我们在$[0,m-1]$上二分，看要形成生成树，需要保留的边权最小值是多少，只要这个边权$\lt k$就存在这种情况。假设此时得到的这个边权属于$index$，它的权值就是最大边权$w$，这种情况下加一的操作数就是$k-w$。

以上两种情况（至少存在一种情况）如果都存在，选择操作数少的那个作为最终答案即可。

复杂度分析

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, m, k, cnt, p[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
        cnt--;
    }
}

bool check(vector<array<int, 3>>& edges, int index) {
    for(int i = 1; i <= n; i++) {
        p[i] = i;
    }
    cnt = n;
    int u = edges[index][1], v = edges[index][2];
    merge(u, v);
    for(int i = 0; i < index; i++) {
        int w = edges[i][0], u = edges[i][1], v = edges[i][2];
        if(find(u) != find(v)) {
            merge(u, v);
        }
    }
    return cnt == 1;
}

void solve(vector<array<int, 3>>& edges) {
    sort(edges.begin(), edges.end());
    int l = m, r = m - 1;
    for(int i = 0; i < m; i++) {
        if(edges[i][0] >= k) {
            l = i;
            break;
        }
    }
    int index = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(edges, mid)) {
            index = mid;
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    LL ans = 1e18;
    if(index != -1) {
        LL temp = 0;
        for(int i = 1; i <= n; i++) {
            p[i] = i;
        }
        cnt = n;
        int w = edges[index][0], u = edges[index][1], v = edges[index][2];
        merge(u, v);
        if(w >= k) {
            temp += w - k;
        }
        for(int i = 0; i < index; i++) {
            int w = edges[i][0], u = edges[i][1], v = edges[i][2];
            if(find(u) != find(v)) {
                merge(u, v);
                if(w >= k) temp += w - k;
            }
        }
        ans = min(ans, temp);
    }
    l = 0, r = m - 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(edges, mid)) {
            index = mid;
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    if(index != -1 && edges[index][0] < k) {
        for(int i = index; i < m && edges[i][0] < k; i++) {
            ans = min(ans, (LL)k - edges[i][0]);
        }
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d%d", &n, &m, &k);
        vector<array<int, 3>> edges;
        for(int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edges.push_back({w, u, v});
        }
        solve(edges);
    }
    return 0;
}