【题目描述】
某个局域网内有n(n≤100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。
【输入】
第一行两个正整数n,k
接下来的k行每行三个正整数i,j,m表示i,j两台计算机之间有网线联通，通畅程度为m。
【输出】
一个正整数，Σf(i,j)的最大值。
【输入样例】
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
【输出样例】
8
1. 题目背景与分析
题目描述：
在一个局域网中，有N台计算机 (N<=100) 和K条网线。由于工作人员疏忽，网络中形成了回路（环），导致数据传输拥堵。每条网线有一个“通畅程度” f(i,j)（权值）。
我们需要拆除一些网线，使得：
网络中没有回路（即变成树或森林结构）。
被拆除网线的权值之和
f(i,j)最大。
核心思路转换：
题目要求“被除去的边权和最大”，这在数学上等价于：
被除去的权值=所有边的总权值- 留下的边权和
为了让“被除去”的最大，我们必须让“留下”的最小。
同时，留下的边必须保证连通且无环。
结论：这道题本质上是求最小生成树。
2. 解法一：Kruskal 算法 (推荐)
为什么推荐 Kruskal？
逻辑直接：Kruskal 算法在遍历边时，如果发现两个点已经连通（find(a) == find(b)），则跳过这条边。跳过的边正是我们要删除的边。我们只需要直接累加这些跳过的边权即可，无需计算总权值再减。
天然支持重边与森林：Kruskal 不需要特殊处理重边（排序后自然处理），也不需要特殊处理非连通图（森林），它会自动处理所有边。
完整代码
//求去除网线的联通度的总和最大，即不被连上的网线边权最大
//所以这道题可以判断出就是求最小生成树（连接上所有计算机）
//没有回路且边权最小
/*
//最佳方法kruskal 对边权从小到大排序后 先连接上的一定是边权较小的
//所以如果有重边，一定是边权较大的没有被连上，即除去的网线的Σf(i,j)最大
//复杂度：O(KlogK) 直接累加被抛弃的边，即为答案。
//prim+邻接矩阵很麻烦，因为邻接矩阵不好保存重边，我们必须先算出总边权，最后再减
#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
struct edge{
int u,v,w;
//边集数组按边权从小到大排序
friend bool operator <(edge a, edge b){
return a.w<b.w;
}
}e[10000];//边集数组
edge mst[10000];//存最小生成树的边
int cnt;//最小生成树的边数
int fa[110];
int idx;//边集数组的有效边（非权值为0）
//并查集查询+路径压缩
int find(int x){
if(fa[x]==x) return x;//如果是根结点就返回
//否则就递归找根节点，并把沿途所有节点跟父节点更新为祖先节点
return fa[x]=find(fa[x]);
}
long long sum;//最小生成树长度
long long sum2;//重复边的边权（Σf(i,j)的最大值）
//并查集链接
void uni(int a,int b){
int faa=find(a);//找a集合中的老大
int fab=find(b);//找b集合中的老大
//如果ab相同无事发生，不同就让a的老大成为b的老大的老大
if(faa!=fab){
fa[fab]=faa;
}
}
void kruskal(){
for(int i=1;i<=idx;i++){
int a=e[i].u;//边集数组第i条边的一个端点
int b=e[i].v;//边集数组第i条边的另外一个端点
//如果a和b没有连通
if(find(a)!=find(b)){//就把他们连上
cnt++;
mst[cnt].u=a;//然后存储边集数组
mst[cnt].v=b;
mst[cnt].w=e[i].w;
sum+=e[i].w;//更新最小生成树长度
uni(a,b);
}
else{//如果a和b已经连通
sum2+=e[i].w;//e[i].w就是被除去网线的Σf(i,j)
}
}
}
int main(){
cin>>n>>k;//n台计算机 k条边
//初始化每个点自成集合
for(int i=1;i<=n;i++) fa[i]=i;
//存储边集数组
for(int i=1;i<=k;i++){
int u,v,w;
cin>>u>>v>>w;
if(w!=0){//w等于代表不存在这条边
e[++idx].u=u;
e[idx].v=v;
e[idx].w=w;
}
}
//对边集数组按边权从小到大排序 这样即使有重复边 也会连接上边权小的
sort(e+1,e+idx+1);
kruskal();
cout<<sum2;
return 0;
}
*/
3. 解法二：Prim
Prim的难点
重边处理：邻接矩阵 g[u][v] 只能存一条边。在读入时，我们需要取 min(w,g[u][v]) 来保留最小边。那些被覆盖掉的较大边权，通过 tot (总权值) 统计，最后减去MST长度时自然就被“删除”了。
非连通图（森林）：标准的 Prim 从一个点（如1号点）开始，只能跑通一个连通块。如果局域网本身就是断开的几块，直接 prim(1) 会漏算其他部分。
解决方案：在 main 函数中遍历所有点，如果 vis[i]==0，说明发现了一个新的连通块，对它执行 prim(i)。
完整代码
//prim+邻接矩阵 复杂度：O(N^2)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;
int g[110][110];
int vis[110];//标记该点是否已经加入集合
long long tot;//一开始给出的所有边的总边权
long long sum;//记录最小生成树的总长度
int dis[110];//每个点到集合的距离
void prim(int s){
dis[s]=0;//起点到集合距离为0
for(int i=1;i<=n;i++){//最多n个点加入集合
int p=0;
//每次在未加入集合的点中找到集合距离最短的
for(int j=1;j<=n;j++){
if(vis[j]==0 && dis[j]<dis[p])
p=j;
}
//如果已经不存在可以加入最小生成树的点就退出
if(p==0 || dis[p]==0x3f3f3f3f) break;
vis[p]=1;//否则就把这个点加入集合
sum+=dis[p];
//然后用这个点去尝试更新所有它的未被点亮的邻接点到集合的距离
for(int j=1;j<=n;j++){
//如果邻接点未被点亮且原本到集合的距离大于经过p到集合的距离
//就更新该距离
if(vis[j]==0 && dis[j]>g[p][j]){
dis[j]=g[p][j];
}
}
}
}
int main(){
cin>>n>>k;//n台计算机 k行
memset(dis,0x3f,sizeof(dis));//初始化每个点到集合的距离为无穷
memset(g,0x3f,sizeof(g));//初始化临界矩阵每个点之间距离为无穷
//邻接矩阵
for(int i=1;i<=k;i++){
int u,v,w;
cin>>u>>v>>w;
tot+=w;
if(w==0) continue;//w为0表示无网线连接
//防止有重边，选择最短的
g[u][v]=g[v][u]=min(w,g[u][v]);
}
//这道题不能直接prim（1），因为可能存在多个连通块，如果直接prim(1)
//如果1-2 3-4 但是12与34之间未连通就是两个连通块，就会漏算
//把34当成要删除的边，所以我们要遍历所有没加入集合的点 计算多个连通块的总sum
//虽然这道题直接prim(1)也能过
for(int i=1;i<=n;i++){
if(vis[i]==0){
prim(i);
}
}
cout<<tot-sum;
return 0;
}
4. 总结与对比
| 特性 | Kruskal算法 | Prim算法 |
| 核心数据结构 | 边集数组+并查集 | 邻接矩阵+距离数组 |
| 处理重边 | 自动处理（排序后跳过） | 需手动取 min |
| 处理森林 | 自动处理（天然支持） | 需外层加循环遍历所有点 |
| 答案计算 | 直接累加else分支的边 | 计算Total-MST |
| 适用场景 | 稀疏图、需要直接求“非树边”权值时 | 稠密图 (N<=1000) |
对于本题，Kruskal 的思维路径更短，代码更不易出错，是首选解法；但掌握 Prim 处理森林 的技巧（外层遍历 vis）也是非常重要的图论基本功。
