自动搬运

查看原文

来自洛谷，原作者为

	Rocket_raccoon_ **

搬运于2025-08-24 21:41:58，当前版本为作者最后更新于2018-10-30 13:40:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

这里详细介绍一下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;
}