Dark roads题解

rainbow_cat · 2023-11-12 22:15:21 · 题解

原题链接
博客链接

Part.1 题目大意

给定一个无向图，求在删去一些边后仍然使各个点相连的情况下，删去边的边权和最大是多少。

Part.2 思路

很明显，保留下来的是最小生成树，这样就使删去的边权和最大。我们只需要用一个 sum 来表示总边权和，用 ans 表示 MST 的边权和，输出 sum-ans 即可。

Part.3 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
struct node{int x,y,z;}a[maxn];
int father[maxn],n,m,ans,cnt,sum;
void init(){for(int i=1;i<=n;i++)father[i]=i;}//初始化
bool cmp(node x,node y){return x.z<y.z;}
int get(int x)
{
    if(father[x]==x)return x;
    return father[x]=get(father[x]);//路径压缩
}
void merge(int x,int y){if(get(x)!=get(y))father[get(y)]=get(x);}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(true)
    {
        cin>>n>>m;
        if(n==0&&m==0)break;
        sum=0,ans=0,cnt=0;//多测不清空，爆零两行泪
        init();
        for(int i=1;i<=m;i++)
        {
            cin>>a[i].x>>a[i].y>>a[i].z;
            a[i].x++,a[i].y++;//注意题目点是从 0 开始的
            sum+=a[i].z;
        }
        sort(a+1,a+m+1,cmp);
        for(int i=1;cnt<=n-1&&i<=m;i++)
        {
            if(get(a[i].x)!=get(a[i].y))
            {
                merge(a[i].x,a[i].y);
                cnt++;
                ans+=a[i].z;
            }
        }
        cout<<sum-ans<<'\n';        
    }
    return 0;
}