ABC218E Destruction题解

题意

给你一个 \(n\) 个点 \(m\) 条边的带权无向联通图，你可以删去任意条边，要求保证图联通的情况下删去边的权值和最大。

\((n\le2\cdot10^5\,\ m\le2\cdot10^5\,\ -10^9\le e_i\le10^9)\) (\(e_i\) 为边权)

分析

首先我们考虑边权全为正的情况，那么我们删除的边肯定是越多，边权越大越好，而使一个有 \(n\) 个点的无向图联通，最少需要 \(n-1\) 条边，也就是树形态，在此基础上，我们希望我们 删除的边权值和最大，也就是树中权值和最小，那么我们就很自然的想到了最小生成树，那么我们肯定是优先考虑选择边权小的边作为树边，那么 Kruskal 算法可以完美完成我们的要求，直接按边权从小到大排序，然后尽量选择边权小的边作为树边。

然后我们发现边权可能为负数，因为删除它们会使我们的答案变小，所以我们在最小生成树的基础上直接不删除负边即可。

AC Code(带注释)

#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0,w=0;char c=0;
    while(!isdigit(c)) {w|=c=='-';c=getchar();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
long long n,m,t,ans;
struct num{
	long long u,v,w;
	bool operator <(const num&a)const{
		return w<a.w;
	}//重载运算符,也可以单独写sort的cmp函数
}e[200050];
int f[200050];
bool vis[200050];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
inline bool merge(int x,int y){
	int A=find(x),B=find(y);
	if(A!=B){
		f[A]=B;
	}
	return A!=B;//如果之前两个点不在同一个联通块中，选择这条边，合并两个并查集
}
//并查集维护Kruskal
inline void Kruskal(){
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		vis[i]=merge(e[i].u,e[i].v);//标记被选择的边
	}
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		e[i].u=read();
		e[i].v=read();
		e[i].w=read();
	}
	sort(e+1,e+m+1);//按边权从大到小排序
	Kruscal();
	for(int i=m;i>=1;i--){
		if(vis[i]){
			continue;//树边不能删
		}
		if(e[i].w<=0){
			break;//不选择负数,因为从后面枚举前面的边权都不大于当前边权,所以可以直接break
		}
		ans+=e[i].w;
	}
	printf("%lld",ans);
	return 0;
}