题目描述
现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。
输入输出格式
输入格式：
第一行包含两个正整数n和k。
第二行包含k个整数，表示哪个城市别敌军占领。
接下来n-1行，每行包含三个正整数a,b,c，表示从a城市到b城市有一条公路，以及破坏的代价c。城市的编号从0开始。
输出格式：
输出一行一个整数，表示最少花费的代价。
输入输出样例
输入样例#1： 复制
5 3 1 2 4 1 0 4 1 3 8 2 1 1 2 4 3
输出样例#1： 复制
4
说明
【数据范围】
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()); }
