[Leaf] [P2700] 逐个击破

p2700-逐个击破---洛谷">P2700 逐个击破 - 洛谷

1. 题面梗概

中译中: 给一张带权图，其中有 $k$ 个城市被敌人占领。现在要删掉一些边，使得这 $k$ 个城市彼此之间都不连通。求删掉边的最小权值和。

2. 逻辑推导

首先是连通性，我们考虑使用并查集维护。其次是删边的最小权值和，看起来像最小割，但数据规模不符合，我们需要换个角度。

2.1 逆向思维

最小化删掉的边权 $\iff$ 最大化保留的边权。

题目要求被占领的城市互不联通，而并查集不适用于删边这种模型。

我们同样反过来想，那不就是如何加边，在保证被占领的城市不联通的情况下，加入的边权和最大呢？

2.2 MST

那么这就是一个最大生成树林问题。我们就可以很轻松用 $Kruskal$ 来解决这个问题。

将边按边权降序排序，然后判断 $(u, v)$ 是不是都是敌人，如果都是敌人，这条边就不能连，不然就让敌人联通了。

2.3 结论

这是个 并查集 + MST 问题。（虽然并查集是 Kruskal 的基础，但这题用到了并查集的时光倒流思维）。

3. 代码实现

▶

AcCode

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

const int maxn = 1e5 + 50;

struct Edge { 
    int u, v; ll w;
    bool operator < ( const Edge &oth ) const { return w > oth.w; }
} edges[maxn];
int edge_cnt;

bool is_enemy[maxn];
int fa[maxn];
ll mst_weight;
int n, k;

int find( int x )
{
    if( fa[x] == x ) return fa[x];
    else return fa[x] = find( fa[x] );
}

void kruskal( )
{
    sort( edges + 1, edges + edge_cnt + 1 );

    for( int i = 1; i <= edge_cnt; ++ i )
    {
        auto [u, v, w] = edges[i];
        
        int fu = find( u ), fv = find( v );
        if( is_enemy[fu] && is_enemy[fv] ) continue;
        fa[fu] = fv;
        if( is_enemy[fu] ) is_enemy[fv] = 1;
        mst_weight += w;
    }
}

void solve( )
{
    cin >> n >> k;

    for( int i = 1; i <= n; ++ i ) fa[i] = i;
    for( int i = 1; i <= k; ++ i )
    {
        int city;
        cin >> city;
        is_enemy[city] = 1;
    }

    ll sum = 0;
    for( int i = 1; i <= n - 1; ++ i ) 
    {
        int u, v; ll w;
        cin >> u >> v >> w;
        edges[++ edge_cnt] = { u, v, w };
        sum += w;
    }

    kruskal( );
    cout << sum - mst_weight << endl;
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( M \log M )$。

• 碎碎念：本题的关键在于正难则反，逆向思维不仅在数据结构专题有效，在图论中同样很重要。

• 关联笔记：生成树理论 | 并查集理论