洛谷题单指南-最小生成树-P2700 逐个击破

原题链接：https://www.luogu.com.cn/problem/P2700

题意解读：n个节点n-1条边的带权图，其中有k个节点标记为敌军，删掉一些边，使得k个敌军节点互补连通，求删除的边权值之和最小值。

解题思路：

1、问题分析

换一个角度，要求删除多少边使得k个节点互不连通，不如在一个图中挑选一些边，使得形成k个连通块，并且k个敌军节点互不连通，剩下

的边就是要删除的边，要让剩下的边最小，必须让挑选的边最大。

2、算法思路

挑选尽可能大的边，使得图中形成k个连通块，且已标识为敌军的k个节点互相不连通，借助于最大生成树的思想，加上并查集处理即可解决。

将k个敌军用hash数组保存，h[i]=true表示节点i是敌军节点
从大到小处理边，对于每一条边u->v，找到u所在连通块的并查集根节点a，v所在连通块的并查集根节点b
如果a和b都是敌军节点，则不允许将a、b连通
如果a和b有一个是敌军节点，则可以将其连通，并查集合并时将敌军节点作为根，累加已挑选边
如果a和b都不是敌军节点，则可以将其连通，累加已挑选边
用总的边权和-已挑选边权和即得到答案
100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100005;
struct Edge
{
    int u, v, w;
    bool operator < (const Edge &e) const
    {
        return w > e.w; //权值从大到小处理
    }
} edges[N];
int p[N];
bool h[N]; //标识敌军的位置
int n, k;
LL sum1, sum2; //sum1是所有权值之和，sum2是不会连通k个敌军的权值之和

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= k; i++)
    {
        int x;
        cin >> x;
        h[x] = true;
    }
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i < n; i++)
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        sum1 += edges[i].w;
    }
    sort(edges + 1, edges + n);
    int cnt = n;
    for(int i = 1; i < n; i++)
    {
        int a = find(edges[i].u);
        int b = find(edges[i].v);
        if(h[a] && h[b]) continue; //如果边的两点所在连通块的根节点都是敌军位置，不能连通
        if(h[a]) p[b] = a; //用已标识敌军的节点a作为根节点
        else p[a] = b; //用已标识敌军的节点b作为根节点，或者b也不是敌军节点就直接连通
        sum2 += edges[i].w;
        if(--cnt == k) break;
    }
    cout << sum1 - sum2 << endl;
    return 0;
}