删边权和最大等价于保留边权和最小，而连通且无环的保留边正是一棵生成树，于是答案 = 总边权和 − 最小生成树边权和，用 Kruskal 加并查集 O(k log k) 求出。
OJ: roj
题目 ID: 1391
难度:普及
标签:图论最小生成树并查集贪心python
创建: 2026-09-30 08:20
更新: 2026-10-07 13:50
后置题目
luogu P1991无线通讯网B 的 Kruskal 聚类直接复用 A 教的按边权升序扫描 + 并查集合并两端连通块这一步，只把停止条件从并满 n-1 条边改成连通块数降到 S；A 是普及的基础 MST 模板，B 为普及/提高- 且额外叠加完全图建边、欧氏距离与卫星电话的聚类建模。luogu P1195口袋的天空B 的 main.cpp 直接复用 A 教的 Kruskal 骨架——边按权升序用并查集判环、两端不同块才合并（unite 失败即 continue），只是把终止条件从连成 1 棵树改成停在 K 个连通块并补一个 No Answer 判断，属于在 A 的并查集判环步骤上叠加额外流程。luogu P2872[USACO07DEC] Building Roads SB 把 A 教的 Kruskal 判环步骤照搬到主解：先并查集合并已有道路，再对完全图候选边按长度排序，只保留连接两个不同连通块的边累加长度
题目描述
局域网内有
输入第一行两个正整数
| 输入样例 | 输出样例 |
|---|---|
5 5 / 1 2 8 / 1 3 1 / 1 5 3 / 2 4 5 / 3 4 2 |
8 |
思路
删去的权值和等于总权值和减去保留的权值和，所以要让删去的最大，只需让保留的最小；而保留的网线无回路且保持连通，恰好是一棵生成树。于是问题化为求最小生成树：把边按权值升序排序，用并查集判断两端点是否已连通，未连通就保留并合并，否则会成环、必须删掉。答案即总权值和减去最小生成树权值和。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 08:20
# update_at: 2026-09-30 08:24
import sys
from collections.abc import Iterable
def mst_weight(n: int, edges: list[tuple[int, int, int]]) -> int:
"""返回最小生成树的边权和；图不连通时只算能连通部分的最小生成森林。"""
parent = list(range(n + 1)) # 并查集：parent[x] == x 表示 x 还是一个集合的根
def find(x: int) -> int:
"""返回 x 所在集合的根，顺手做路径压缩。"""
while parent[x] != x:
parent[x] = parent[parent[x]] # 隔代压缩，写起来比递归浅
x = parent[x]
return x
total = 0
used = 0 # 已并入生成树的边数，等于 n-1 时整张图已经连通
for w, u, v in sorted(edges): # 元组排序先比 w，权重升序就是 Kruskal 的贪心顺序
ru, rv = find(u), find(v)
if ru == rv:
continue # 两端已经连通，这条边加上去正好成环，必须删掉
parent[ru] = rv
total += w
used += 1
if used == n - 1:
break
return total
def solve() -> None:
data: Iterable[int] = map(int, sys.stdin.buffer.read().split())
it = iter(data)
n, k = next(it), next(it)
edges = []
total = 0
for _ in range(k):
i, j, m = next(it), next(it), next(it)
edges.append((m, i, j)) # 权重放到第 0 位，Kruskal 直接按元组排序即可
total += m
keep = mst_weight(n, edges)
print(total - keep) # 总量固定，留下的越少被删掉的越多
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 12:30
* update_at: 2026-10-05 12:30
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXK = 10005; // n<=100，最多 n*(n-1)/2 条边，开大一倍留余量
struct Edge {
ll w; // 通畅程度，越小越通畅
ll u;
ll v;
};
Edge edge[MAXK]; // 保存所有网线，Kruskal 按 w 升序扫描
ll parent[105]; // 并查集：parent[x] 表示 x 所在集合的父节点
// 返回 x 所在集合的根，路径压缩
ll find_root(ll x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// Kruskal 的排序标准：按通畅程度升序
bool cmp_edge(Edge a, Edge b) {
return a.w < b.w;
}
int main() {
ll n, k;
scanf("%lld %lld", &n, &k);
ll total = 0; // 所有网线通畅程度之和，是常数部分
for (ll e = 1; e <= k; e++) {
scanf("%lld %lld %lld", &edge[e].u, &edge[e].v, &edge[e].w);
total = total + edge[e].w;
}
sort(edge + 1, edge + k + 1, cmp_edge);
for (ll i = 1; i <= n; i++) {
parent[i] = i; // 初始时每台计算机自成一个集合
}
ll keep = 0; // 最小生成树的权值和
ll used = 0; // 已并入生成树的边数，达到 n-1 时全图已连通
for (ll e = 1; e <= k; e++) {
ll ru = find_root(edge[e].u);
ll rv = find_root(edge[e].v);
if (ru == rv) {
continue; // 两端已连通，留下这条边会成环，必须删掉
}
parent[ru] = rv;
keep = keep + edge[e].w;
used++;
if (used == n - 1) {
break;
}
}
// 删边权和最大 = 总权值和 - 保留的最小权值和
printf("%lld\n", total - keep);
return 0;
}