【洛谷】P2820 局域网

题目链接：P2820 局域网 – 洛谷

题目简述

去除 $k$ 个边中的最大回路边。

思路

在输入的时候统计权重总和，减去最小生成树的总和。

• 这道题用简单数组实现 Prim，复杂度是 $O(n^2)$；
• 用堆优化的 Prim 是 $O(k\log n)$；
• Kruskal 则是 $O(k\log k)\approx O(k\log n)$。

在本题规模下（$n\le100$、最坏 $k\approx4950$），这两种算法都可以解决，但Kruskal+并查集更加直观简洁。

代码

//
// Created by xiaoeyv on 2025/6/19.
//

#define maxn 110
#define maxm (maxn * (maxn-1))/2
#include<bits/stdc++.h>
using namespace std;

int pre[maxn], r[maxn], sz[maxn];
bool vis[maxn];

int n, k;
int cnt = 0;
int ans = 0;

struct Edge {
    int u, v, w;
} e[maxm];

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

void join(int x, int y) {
    int rx = find(x), ry = find(y);
    if ( rx == ry )
        return;
    if ( r[rx] < r[ry] )
        pre[rx] = ry;
    else {
        pre[ry] = rx;
        if ( r[rx] == r[ry] )
            r[rx]++;
    }
}

int main() {
    cin >> n >> k;
    memset(r, 0, sizeof(r));
    memset(sz, 0, sizeof(sz));
    for (int i = 0; i <= n; i++)
        pre[i] = i;
    for (int i = 1; i <= k; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ans += w;
        e[i].u = u, e[i].v = v, e[i].w = w;
    }
    sort(e + 1, e + k + 1, [](const auto &x, const auto &y) {
        return x.w < y.w;
    });
    for (int i = 1; i <= k && cnt < n - 1; i++) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int ru = find(u), rv = find(v);
        if (ru != rv) {
            join(u, v);
            ans -= w;
            cnt++;
        }
    }
    cout << ans << endl;
    return 0;
}