题目描述
现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。
输入输出格式
输入格式：
第一行包含两个正整数n和k。
第二行包含k个整数，表示哪个城市别敌军占领。
接下来n-1行，每行包含三个正整数a,b,c，表示从a城市到b城市有一条公路，以及破坏的代价c。城市的编号从0开始。
输出格式：
输出一行一个整数，表示最少花费的代价。
输入输出样例
说明
【数据范围】
10%的数据：2≤n≤10；
100%的数据：2≤n≤100000，2≤k≤n，1≤c≤1000000。
要求的是拆掉最短的路使得给出的点分割
很容易想到用最小生成树来做
但是正面做很难处理 比如 1-2-3-4 假如1和4是要分隔的点 很难确定该怎么拆边
可以把这题反过来看：要求的是拆掉最短的路使得给出的点分隔 反过来就是 所有路的权值-（假设一开始都没有连接）连上最大的路使得给出的点是分隔状态 （其实就是把所有不“关键”路连上 留下的是关键路的最小权值）
显然要从大到小排列 “最大”生成树
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define LL long long #define pb push_back #define fi first #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) /////////////////////////////////// #define inf 0x3f3f3f3f #define N 100000+5 int f[N]; int vis[N]; int n; int find1(int x) { return f[x]==x?x:find1(f[x]); } struct node { int s,e,v; }edge[N]; bool cmp(node a,node b) { return a.v>b.v; } long long kruskal(void ) { long long ans=0; sort(edge+1,edge+n-1,cmp); rep(i,1,n-1) { int a=find1(edge[i].s); int b=find1(edge[i].e); int c=edge[i].v; if(vis[a]&&vis[b])continue; if(!vis[a]&&!vis[b]) { ans+=c; f[a]=b; continue; } //剩下的最后两种情况 ans+=c; f[a]=b; vis[find1(a)]=1; } return ans; } int main() { int m; RII(n,m); rep(i,0,n) f[i]=i; while(m--) { int x;RI(x); vis[x]=1; } long long sum=0; rep(i,1,n-1) { RIII(edge[i].s,edge[i].e,edge[i].v); sum+=edge[i].v; } printf("%lld",sum-kruskal()); }