局域网题目

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) #最小生成树 T2

题目描述

某个局域网内有$n(n\le 100)$台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。

因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用$f(i,j)$表示$i,j$之间连接的畅通程度$(f(i,j)\le 1000)$，$f(i,j)$值越小表示$i,j$之间连接越通畅，$f(i,j)$为$0$表示$i,j$之间无网线连接。

现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的$\Sigma f(i,j)$最大，请求出这个最大值。

输入

第一行两个正整数$n,k$

接下来的$k$行每行三个正整数$i,j,m$表示$i,j$两台计算机之间有网线联通，通畅程度为$m$。

输出

一个正整数，$\Sigma f(i,j)$的最大值。

输入样例

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

输出样例

8

思路

在存在环无向图中去除一些边, 使得剩下的边权值总和最小（去掉的最大）, 而且依旧连通。

直接求一边最小生成树就可以实现在所有边中构建出权值和最小的选择方案。

这里用Kruscal算法来写。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e2 + 10, M = 220;
int n, m;
int f[N];
 
struct Node
{
    int a, b, c;
    bool operator<(const Node &w) const
    {
        return c < w.c;
    }
} e[M];
 
int find(int x)
{
    return f[x] == x ? f[x] : f[x] = find(f[x]);
}
 
int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
    }
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; i++)
    {
        int a = find(e[i].a), b = find(e[i].b), c = e[i].c;
        if (a != b)
            f[b] = a;
        else
            res += c;
    }
    cout << res << endl;
    return 0;
}