题目描述

某个局域网内有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)最大，请求出这个最大值。

思路

这题一看就知道是最小生成树，将全部的边权加起来以后减去最小生成树的值就是答案

#include <stdio.h>
#include <algorithm>
using namespace std;
int f[1001];
struct arr
{
    int x,y,z;
};
arr a[1001];
int cam(arr x,arr y)
{
    return x.z<y.z;
}
int find(int x)
{
    if (!f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
int insert(int x,int y)
{
    if (find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n,m;
    long long l=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        l+=a[i].z;
    }
    sort(a+1,a+m+1,cam);
    long long tot=0;
    for (int i=1;i<=m;i++)
    {
        if (find(a[i].x)!=find(a[i].y))
        {
            tot+=a[i].z;
            insert(a[i].x,a[i].y);
        }
    }
    printf("%lld\n",l-tot);
}