题解 P2820 【局域网】

· · 题解

先分析一下题目，要使删去的边最大，等价于使剩下的边长度最小。

那么就可以使用最小生成树求解此题，只需要在输入时算出边长总和，再减去最小生成树的长度就行了。

这里详细介绍一下Kuskal算法。

首先，既然要求“最小生成树”，那我们就对所有边进行排序（使用sort的话非常简便）。但还要处理一个问题，那就是我怎么知道我加上的这条边是不是我需要的呢？

于是这就牵涉到一个简单却作用很大的算法“并查集”，不会的同学戳这里

Kuskal主要是针对排序边的贪心算法，可以想一下，既然是要求使图相连通，那么把现在没有连通的点用现在所拥有的边连上肯定不会错。

具体详见代码

#include<iostream>
#include<cstdio>
#include<algorithm>//sort所需要的STL头文件
using namespace std;
int n,m,f[200],ans,x,sum;
struct lol{
    int from,to,val;//使用结构体存储边的两端点，长度
}l[20010];
bool cmp(lol a, lol b){
    return a.val<b.val;//sort排序设置边长为关键字
}
int find(int x){
    if (f[x]==x) return x;
    else return f[x]=find(f[x]);//并查集
}
void Kuskal(){
    int a,b;
    sort(l+1,l+1+m,cmp);//sort快排
    for (int i=1; i<=m; i++){
        a=find(l[i].from); b=find(l[i].to);//找两点的祖先
        if (a==b) continue;//ab在同一集合，即a，b点已连通，则跳过
        sum+=l[i].val;//记录长度
        f[a]=b;//合并
        x++;
        if (x==n) return;//边达到需要值，跳出函数
    }
}
int main(){
    int i;

    cin>>n>>m;

    for (i=1; i<=n; i++){
        f[i]=i;
    }
    for (i=1; i<=m; i++){
        scanf("%d%d%d",&l[i].from,&l[i].to,&l[i].val);
        ans+=l[i].val;//算总长
    }
    Kuskal();

    printf("%d",ans-sum);//输出

    return 0;
}