逐个击破 | FFY's Blog

题意

现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。

题解

我们加一个辅助数组记录每个城市是否被占领,然后跑最大生成树.当且仅当两个城市所在的连通块都被占领时,我们不取这条边,其余时候将当前两个城市的占领属性合并,最后 $ans$=用总代价-最大生成树权值和

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
int n,k,fa[maxn];
ll ans;
bool ee[maxn];
struct fy
{
    int from,to,d;
    bool operator<(const fy&a)
    const{return d>a.d;};
}q[maxn];
int find(int a)
{
    while(a!=fa[a])a=fa[a]=fa[fa[a]];
    return a;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        int a;
        scanf("%d",&a);
        ee[a]=true;
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&q[i].from,&q[i].to,&q[i].d);
        ans+=q[i].d;
    }
    sort(q+1,q+n);
    for(int i=1;i<n;i++)
    {
        int a=find(q[i].from);
        int b=find(q[i].to);
        if(ee[a]&&ee[b])continue;
        fa[a]=b;
        ee[a]|=ee[b];ee[b]|=ee[a];//合并属性
        ans-=q[i].d;
    } 
    printf("%lld\n",ans);
    return 0;
}