【Ybtoj 第10章例6】逐个击破【并查集】

本文主要是介绍【Ybtoj 第10章例6】逐个击破【并查集】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

解题思路

把公路看作边，把城市看作点，被占领的城市看做特殊点，这道题就被转化成求是特殊点相互不联通的最优删减方案。
首先我们换个方向，不删边，改成连边，变为这样一个贪心：先按边权降序排列，然后从前往后枚举所有边，如果某一条边连接后不会使两个特殊点联通，就连上这条边。最后答案为总边权值减去连接过的边权和。

考虑优化时间复杂度：
我们发现，一个连通块中最多有一个特殊点或者没有，我们可以用并查集来维护连通块。如果集合中存在特殊点，则令特殊点为集合的代表元素，否则任意一点都就可以。判断一条边是否会是两个特殊点联通，直接判断两端点所在的集合代表元素是否为特殊点即可，而判断两点是否联通直接判断所在集合的代表元素是否相同即可。两个及和合并时，如果其中有一个集合的代表元素为特殊点，就把另一个集合并入其中，以保证特殊点总是其所在集合的代表元素。

代码

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;int n,m,k,x,l[100010],fa[100010];
long long ans;struct c{int u,v,w;
}a[500010];bool cmp(c l,c r)
{return l.w>r.w;
}int find(int x)
{if(x==fa[x])return x;else return fa[x]=find(fa[x]);
}int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=k;i++){scanf("%d",&x);l[x+1]=1;}for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);a[i].u++,a[i].v++;//因为从0开始ans+=a[i].w;}	sort(a+1,a+m+1,cmp);for(int i=1;i<=m;i++){int xx=find(a[i].u),yy=find(a[i].v);if(xx==yy)ans-=a[i].w;else if(!l[xx]||!l[yy])//至少有一个集合的代表元素不是特殊点{ans-=a[i].w;if(!l[xx])fa[xx]=yy;//并入特殊点所在的那个集合else fa[yy]=xx;}}printf("%lld",ans);
}