【YBTOJ】逐个击破

思路：

我们可以把题目转化成，现在有一些各不连通的点，然后要联通其中一些边，使得特殊点不在一个连通块里，然后求最大的连边权值
我们可以贪心暴力，每次考虑连最大的边，然后判断两个连通块是否都有特殊点，如果都有那就不连，如果其中一个有，那就把没有的那个连向那个有的，这样就可以保证没有的那个连通块每次找到的最终祖先都是那个有特殊点的最终祖先。

$code$

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;int n, m, k;
int fa[1001000];
bool v[1001000];
struct node
{int x, y, z;
}a[100100];bool cmp(node x, node y)
{return x.z>y.z;
}int find(int x)
{if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}int main()
{scanf("%d%d%d", &n, &m, &k);//m=n-1;for(int i=1; i<=k; i++){int x;scanf("%d", &x);v[x]=1;}for(int i=0; i<=n; i++)fa[i]=i;long long ans=0;for(int i=1; i<=m; i++){scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);ans+=a[i].z;}sort(a+1, a+1+m, cmp);for(int i=1; i<=m; i++){int fx=find(a[i].x);int fy=find(a[i].y);if(fx==fy){ans-=a[i].z;continue;}else if(!v[fx]&&!v[fy]){ans-=a[i].z;fa[fx]=fy;continue;}else if(v[fx]&&!v[fy]){ans-=a[i].z;fa[fy]=fx;continue;}else if(!v[fx]&&v[fy]){ans-=a[i].z;fa[fx]=fy;continue;}}printf("%lld", ans);return 0;
}