题面

各大 \(OJ\) 都有

分析

从结果入手：所有被敌方军团占领的城市都是分开的

而按最小代价删去若干条边，则剩下的图必然是若干个联通子图组成的

那么我们要使花费最小，可以是留下的边最大

并查集合并两个敌方军团和不大于一集合即可

\(Code\)

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

int n , k , vis[N] , fa[N];

LL ans , sum;

struct edge{

	int x , y , z;

}e[N];

bool cmp(edge a , edge b){return a.z > b.z;}

int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}

int merge(int u , int v)

{

	int x = find(u) , y = find(v);

	if (vis[x] && vis[y]) return 0;

	if (vis[x]) fa[y] = fa[x];

	else fa[x] = fa[y];

	return 1;

}

int main()

{

	scanf("%d%d" , &n , &k);

	int x , y , z;

	for(register int i = 1; i <= k; i++) scanf("%d" , &x) , vis[x + 1] = 1;

	for(register int i = 1; i < n; i++)

		scanf("%d%d%d" , &x , &y , &z) , e[i] = edge{++x , ++y , z} , ans += (LL)z;

	sort(e + 1 , e + n , cmp);

	for(register int i = 1; i <= n; i++) fa[i] = i;

	for(register int i = 1; i < n; i++)

		if (merge(e[i].x , e[i].y)) sum += (LL)e[i].z;

	printf("%lld" , ans - sum);

}

巴特西

JZOJ 2936. 【NOIP2012模拟8.9】逐个击破

题面

分析

\(Code\)

最新文章

热门文章