逐个击破

flatte / 2023-07-28 / 原文

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

第一行包含两个正整数n和k 。

第二行包含 k个整数，表示k个敌军占领的城市。

接下来n-1行，每行包含三个正整数a,b,c表示从 a 城市到 b 城市有一条公路，以及破坏的代价c 。城市的编号从0 开始。

输出一行一个整数，表示最少花费的代价。

样例输入

样例输出

对于10% 的数据：2<=n<=10；

对于100% 的数据：2<=k<=n<=10⁵,1<=c<=10⁶，。

删边没思路，我们反向考虑连边，每连一条边后都保证不会将敌人的城市连通。

我们按边权值从大到小的顺序来决定是否连边，连边时将两个端点加入同一个集合（并）

如果某条边的两个端点分别与敌人的占领的两个不同城市连通，那么这条边不能连。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
typedef long long LL;

LL ans;
struct node {
    int u,v,d;
} a[MAXN];

int n,k,fa[MAXN];
bool enemys[MAXN];//enemys[i]==true 表示i城市被敌人占领

bool cmp(const node &x, const node &y) { return x.d > y.d; }

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

int main() {	
    cin>>n>>k;
    for(int i=0;i<k;i++) {
    	int x;	
		cin>>x;
		enemys[x]=true;					
	}
	
    for (int i = 0; i < n; i++) fa[i]=i;   
    
    for (int i = 1; i < n; i++) {
    	
        cin >> a[i].u >> a[i].v >> a[i].d;
        ans+=a[i].d;			//累计删除所有边的代价

    }
    
	sort(a + 1, a  + n, cmp);

    for (int i = 1; i < n; i++) 
	{
    	
       int u=a[i].u;
       int v=a[i].v;
       int d=a[i].d;
       
       int fau=find(u),fav=find(v);
       
        if (fau==fav) //存在连通uv的路径
	   		ans-=d;  //uv这条边就别删了
			   	   		
	   	else if(!enemys[fau] || !enemys[fav]) //u城所在集合中没有敌人城市 或者  v城所在集合中没有敌人城市，那么uv边没必要删除
		   {
		   		ans-=d;
		   		if(enemys[fau]) fa[fav]=fau;//u城所在集合中有敌人城市，v并入u集合
		   		else fa[fau]=fav;			//u城所在集合中没有敌人城市，或者uv集合中都没有敌人城市，u并入v集合
		   	
		   } 
    
	}
	cout << ans << endl;
    return 0;
}