【ybt】【图论 并查集 课过 例6】逐个击破

逐个击破

题目链接：逐个击破

题目描述

解题思路

我们可以反过来想：我们现在有一些城市，需要把这些城市连成多个并查集，每个并查集中只能有一个敌方城市，要求花费最多。

我们排序，贪心即可。

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;int n,m,k,ans;
int v[100010];struct abc{int x,y,z;
}a[500010];struct abcd{int fa,flag;
}fa[100010];bool cmp(abc a,abc b)
{return a.z>b.z;
}abcd fd(int now)
{if(fa[now].fa==now)return fa[now];return fa[now]=fd(fa[now].fa);
}signed main()
{cin>>n>>k;for(int i=0;i<n;i++)fa[i].fa=i;for(int i=1;i<=k;i++){int t;scanf("%lld",&t);v[t]=1;fa[t].flag=1;}for(int i=1;i<n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z),ans+=a[i].z;sort(a+1,a+n,cmp);for(int i=1;i<n;i++){int fx=fd(a[i].x).fa;int fy=fd(a[i].y).fa;if(fx==fy){ans-=a[i].z;continue;}if(!(fa[fx].flag&&fa[fy].flag)){if(fa[fx].flag==1)fa[fy].fa=fx;elsefa[fx].fa=fy;ans-=a[i].z;}}cout<<ans<<endl;
}