局域网(net)（信息学奥赛一本通- P1391）

【题目描述】

【输入】

【输出】

【输入样例】

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)（权值）。

我们需要拆除一些网线，使得：

1. 网络中没有回路（即变成树或森林结构）。

2. 被拆除网线的权值之和f(i,j)最大。

核心思路转换：

题目要求“被除去的边权和最大”，这在数学上等价于：

被除去的权值=所有边的总权值- 留下的边权和

为了让“被除去”的最大，我们必须让“留下”的最小。

同时，留下的边必须保证连通且无环。

结论：这道题本质上是求最小生成树。

2. 解法一：Kruskal 算法 (推荐)

为什么推荐 Kruskal？

1. 逻辑直接：Kruskal 算法在遍历边时，如果发现两个点已经连通（find(a) == find(b)），则跳过这条边。跳过的边正是我们要删除的边。我们只需要直接累加这些跳过的边权即可，无需计算总权值再减。

2. 天然支持重边与森林：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的难点

1. 重边处理：邻接矩阵g[u][v]只能存一条边。在读入时，我们需要取min(w,g[u][v])来保留最小边。那些被覆盖掉的较大边权，通过tot(总权值) 统计，最后减去MST长度时自然就被“删除”了。

2. 非连通图（森林）：标准的 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 处理森林的技巧（外层遍历vis）也是非常重要的图论基本功。