逐个击破

wjh15101051's space

卧薪尝胆，厚积薄发。

逐个击破

Date: Wed Oct 10 18:27:57 CST 2018

In Category: NoCategory

Description：

给一棵树，有 $k$ 个关键点，每条边有边权，要想让关键点两两不相连，最小化删掉的边权和。

$1\leqslant n\leqslant10^5$

Solution：

删边不好做，我们可以按边权从大到小依次加边，同时保证关键点两两不相连，最后剩下没加的就是最小边权和，可以维护一个 $g[i]$ 表示 $i$ 这个联通块是否有关键点，如果某条边的两边都有，就不合并。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

bool g[MAXN];

int f[MAXN];

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

struct edge

{

	int u,v,w;

}e[MAXN];

bool cmp_w(edge a,edge b){return a.w > b.w;}

int main()

{

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

	int x;

	for(int i = 1;i <= k;++i)

	{

		scanf("%d",&x);

		g[x] = true;

	}

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

	long long s = 0;

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

	{

		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

		s += e[i].w;

	}

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

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

	{

		int p = find(e[i].u),q = find(e[i].v);

		if(p == q)continue;

		if(g[p] && g[q])continue;

		f[p] = q;g[q] |= g[p];

		s -= e[i].w;

	}

	cout << s << endl;

	return 0;

}

In tag: 数据结构-并查集

wjh15101051