http://tyvj.cn/p/3737
时间: 1000ms / 空间: 131072KiB / Java类名: Main
描述
秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面：
现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。
输入格式
第一行包含两个正整数n和k。
第二行包含k个整数，表示哪个城市别敌军占领。
接下来n-1行，每行包含三个正整数a,b,c，表示从a城市到b城市有一条公路，以及破坏的代价c。
城市的编号从0开始计数。
其中：
2<=n<=100000
2<=k<=n
1<=c<=1000000
输出格式
包含一个整数，表示最少花费的代价。
测试样例1
输入
3 3
0 1 2
0 1 1
1 2 2
输出
3
测试样例2
输入
5 3
1 2 4
1 0 4
1 3 8
2 1 1
2 4 3
输出
4
破坏的最少=留下的最多，
使最多一个敌军驻地包含在内一个连通子图内
做最大生成树，需要合并连个同在敌占区的组合时，这条边就是应该被破坏的。
例如：7-9不需要破坏，将9并入敌占区；
6-7不需要破坏，将6并入敌占区；
6，8同在敌占区， 6-8 需要破坏，这是连接7，8的最短路。
同理，将5并入敌占区
将1，2，4并入3对应的敌占区；
最后，将4-5切断。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Size 100005 int n,k;
struct edge{
int u,v,w;
}eg[Size];
long long ans=;
bool tag[Size]; int pa[Size];
void init(){
for(int i=;i<=n;i++)pa[i]=i;
}
int find(int x){
if(pa[x]!=x)pa[x]=find(pa[x]);
return pa[x];
} bool ff(edge a,edge b){
return a.w>b.w;
} void kruskal(){
init();
sort(eg+,eg+n,ff); for(int i=;i<=n-;i++){
int x=find(eg[i].u);
int y=find(eg[i].v);
if(tag[x]&&tag[y]){
ans+=eg[i].w;
}
else{
tag[y]=tag[x]||tag[y];
pa[x]=y;
}
}
} int main(){
scanf("%d%d",&n,&k);
int x;
for(int i=;i<=k;i++){
scanf("%d",&x);
tag[x]=true;
}
for(int i=;i<=n-;i++){
scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);
}
kruskal();
printf("%lld",ans);
}
注意一定用scanf
用cin超时。。。