逐个击破

题目

Description

三大战役的平津战场上，傅作义集团在以北平、天津为中心，东起唐山西至张家口的铁路线上摆起子一字长蛇阵，并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走，***制定了先切断敌人东洒两头退路然后再逐个歼灭敌人的战略方针。

秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面：

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

Input

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

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

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

城市的编号从0开始计数。

Output

包含一个整数，表示最少花费的代价。

Sample Input

3 3

0 1 2

0 1 1

1 2 2

Sample Output

3

Data Constraint

2<=n<=100000

2<=k<=n

1<=c<=1000000

题解

题意

有n个点，其中有k个点是黑色，剩下点是白色

给出n-1条边，现在要割去某些边使得黑点与黑点之间不相连，问最小代价

分析

逆向思维

构造一棵合法的最大生成树

用总代价减去即可

树的边与边连不连取决于两个集合内黑点的数量，如果相加小于等于1就可以连

Code

#include<bits/stdc++.h>

using namespace std;

struct node

{

	int x,y,z;

}a[100005];

int n,k,x,xx,yy,f[100005],gz[100005],b[100005];

long long s,ans;

bool cmp(node x,node y)

{

	return x.z>y.z;

}

int find(int x)

{

	if (f[x]!=x) f[x]=find(f[x]);

	return f[x];

}

int read()

{

	int res=0;char ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();

	return res;

}

int main()

{

	n=read();k=read();

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

		x=read(),b[x]=1;

	s=0;

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

		a[i].x=read(),a[i].y=read(),a[i].z=read(),s+=a[i].z;

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

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

		f[i]=i;

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

	{

		xx=find(a[i].x);yy=find(a[i].y);

		if (b[xx]+b[yy]<=1)

		{

			b[yy]=b[xx]+b[yy];

			f[xx]=yy;

			ans+=a[i].z;

		}

	}

	printf("%lld\n",s-ans);

	return 0;

}

JZOJ【NOIP2012模拟8.9】2020.10.5 T1的相关教程结束。