题目概述

给定一张无向图，其中前 $ n-1 $ 条边为黑边，其余为白边。我们可以在恰好一条边 $ i $ 的权值变为 $ \max(c_i - d, 0) $ 的条件下，求生成树的最小权值，并在此前提下使白边数量尽可能少。

基本思路

我们考虑使用 Kruskal 算法来求解最小生成树。在排序边时，第一关键字为边权，第二关键字为边的颜色（黑边优先）。这样可以在保证权值最小的前提下，尽可能多地选择黑边。

关键观察

当我们对某一条边进行权值减少 $ d $ 的操作时，根据贪心策略，应选择当前生成树中权值最大的边进行修改。因为：

算法步骤

  1. 第一次 Kruskal
    使用原始边权，按权值小优先、黑边优先的规则，求出最小生成树，记录其最大边权 $ mx $。

  2. 处理可替换边
    将原图中所有边权等于 $ mx $ 的边权值修改为 $ \max(c_i - d, 0) $，并记录这些边。

  3. 处理特殊情况
    如果 $ mx < d $，则可能存在一些边权大于 $ mx $ 但减去 $ d $ 后权值更小的边（“可代替边”）。我们需要将这些边也纳入考虑。

  4. 第二次 Kruskal
    使用修改后的边权再次运行 Kruskal 算法，统计生成树中的白边数量，确保在总权值最小的前提下白边最少。

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL n, m, d, ans, F[200005], p, q;
struct node {
    LL u, v, w, A;
} a[200005];
vector<LL> rec;

bool unite(node P, node Q) {
    if (P.w == Q.w) return P.A < Q.A;
    return P.w < Q.w;
}

LL find(LL x) {
    return F[x] == x ? x : F[x] = find(F[x]);
}

int main() {
    cin >> n >> m >> d;
    for (LL i = 1; i <= n; i++) F[i] = i;
    for (LL i = 1; i <= m; i++) cin >> a[i].u >> a[i].v >> a[i].w, a[i].A = i;
    sort(a + 1, a + m + 1, unite);
    
    for (LL i = 1; i <= m; i++) {
        p = find(a[i].u), q = find(a[i].v);
        if (p == q) continue;
        F[p] = q;
        rec.push_back(a[i].A);
        
        if (rec.size() == n - 1 && a[i].A >= n && a[i].w < d) {
            for (LL j = i + 1; j <= m; j++)
                if (a[j].A <= n && a[j].w <= d) {
                    ans--;
                    break;
                }
            break;
        }
    }
    for (LL i : rec) if (i >= n) ans++;
    cout << ans;
	return 0;
}