题目链接：洛谷 P2820 局域网

题目背景

某局域网中有n(n≤100)台计算机，由于搭建时的疏忽，网络连接形成了回路。这种情况下数据会在回路中不断传输，导致网络卡顿。计算机之间的网线连接通畅程度不同，我们用f(i,j)表示i,j之间的通畅程度，值越小表示连接越通畅，0表示无连接。

题目描述

需要移除部分连线，消除网络中的回路，同时使被移除网线的Σ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

说明

f(i,j)≤1000

解题思路

这个问题本质上是在求图的最小生成树。我们需要理解以下概念：

相关概念：

• 生成树：在一个图中连接所有n个节点的n-1条边形成的树结构
• 最小生成树：在所有可能的生成树中，边权总和最小的树

算法选择：

可以使用Prim算法或Kruskal算法解决此问题。本文将重点介绍Prim算法的实现。

Prim算法原理：

Prim算法采用"红点-白点"思想：初始时，选择一个节点作为红点（已加入生成树），其余节点为白点。每次循环找出距离红点集合最近的白点，将其变为红点，并用该点更新其他白点到红点集合的距离。重复此过程直到所有节点都成为红点。

对于本题，被移除网线的最大总和 = 原图所有边权总和 - 最小生成树的边权总和。

代码实现

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

const int MAXN = 105;
int network[MAXN][MAXN];  // 存储网络连接的邻接矩阵
int dist[MAXN];           // 存储每个节点到生成树的最短距离
bool inTree[MAXN];        // 标记节点是否已在生成树中
int nodeCount, connectionCount;
int totalWeight = 0;      // 原图总权重
int mstWeight = 0;        // 最小生成树权重

int main() {
    cin >> nodeCount >> connectionCount;
    
    // 初始化邻接矩阵
    memset(network, 0, sizeof(network));
    
    // 读取输入并计算总权重
    for (int i = 0; i < connectionCount; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        network[u][v] = network[v][u] = w;
        totalWeight += w;
    }
    
    // 初始化距离数组和标记数组
    memset(dist, 0x7f, sizeof(dist));
    memset(inTree, false, sizeof(inTree));
    
    // 从节点1开始构建最小生成树
    dist[1] = 0;
    
    for (int i = 1; i <= nodeCount; i++) {
        // 找到距离生成树最近的节点
        int nearest = 0;
        for (int j = 1; j <= nodeCount; j++) {
            if (!inTree[j] && ((dist[j] < dist[nearest]) || nearest == 0)) {
                nearest = j;
            }
        }
        
        // 将该节点加入生成树
        inTree[nearest] = true;
        mstWeight += dist[nearest];
        
        // 更新其他节点到生成树的距离
        for (int j = 1; j <= nodeCount; j++) {
            if (network[nearest][j] && !inTree[j]) {
                dist[j] = min(dist[j], network[nearest][j]);
            }
        }
    }
    
    // 计算并输出结果
    cout << totalWeight - mstWeight << endl;
    
    return 0;
}

此代码实现了Prim算法来解决局域网回路问题。通过计算原图总权重与最小生成树权重的差值，得到需要移除的网线最大总和。