10.17_T1 平津战役

题目大意：

有n个点，n-1条边，破坏这条边的代价是已知的，有k个特殊的点，问使这k个点互不相连的最小代价

解题思路：

我们破坏边的最小代价就是建边使得k个点互不相连的最大代价
所以我们不用考虑删边，只考虑如何去建边
也就是说我们要搞一个生成树，用并查集+排序就OK啦~
%%%%爱装蒻的巨佬

Accepted code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 100001

using namespace std;

long long ans;
int n, k, a, b, f[N];
bool vis[N];

struct node {
	int from,to,w;
}e[N];

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

inline bool cmp(node x,node y) { return x.w>y.w; }

inline int read()
{
	char c = getchar(); int d = 1, f = 0;
	while (!isdigit(c)) {d = (c == '-')?(-1):(d); c = getchar();}
	while (isdigit(c)) f=(f<<3) + (f<<1) + c - 48, c = getchar();
	return f * d;
}

int main()
{
	n=read(); k=read(); f[n]=n;
	for(register int i = 1; i <= k; i++) vis[read()]=1;
	for(register int i = 1; i < n; i++)
		e[i] = (node){read(), read(), read()}, f[i]=i, ans+=e[i].w;
	sort(e + 1, e + n, cmp);
	for(register int i = 1; i < n; i++)
	{
		a = find(e[i].from);
		b = find(e[i].to);
		if(vis[a] & vis[b]) continue;
		f[a] = f[b];
		ans -= e[i].w;
		vis[a] = vis[b] = vis[a] | vis[b];
	}
	return printf("%lld\n",ans) & 0;
}