思路与算法

求所有网线权重之和，用Kruskal保留最小生成树（各原连通块内则为最小生成森林），总和减保留权重即最多可删除权重。

正确性说明

保持原连通关系且无环的保留边恰为各块生成树；删除权重=固定总和-保留权重，故最小生成森林使删除值最大。Kruskal安全边交换性质保证保留权重最小。

复杂度

O(k log k+k alpha(n)+n)时间、O(n+k)空间，含边数组和并查集初始化。

易错点

不能直接删光所有边；目标是保留网络连通关系并去环。权重相等不影响答案，树形网络答案0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<tuple<int, int, int>> e;
    long long total = 0;
    while (k--) {
        int a, b, w;
        cin >> a >> b >> w;
        e.push_back({w, a, b});
        total += w;
    }
    sort(e.begin(), e.end());
    DS d(n + 1);
    for (auto z : e) {
        int w, a, b;
        tie(w, a, b) = z;
        if (d.join(a, b))
            total -= w;
    }
    cout << total << "\n";
}