题目地址:HDU 4313
利用最小生成树的思想,这里是从大往下删,能删则删,不能删就留着。用个并查集维护下。代码如下:
#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <string>
#include <time.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
int ha[MAXN], bin[MAXN];
struct node
{
int u, v, w;
bool operator < (const node &tmp) const{
return w>tmp.w;
}
}fei[MAXN];
int find1(int x)
{
return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void init(int n)
{
memset(ha,0,sizeof(ha));
for(int i=1;i<=n;i++){
bin[i]=i;
}
}
int main()
{
int t, n, k, u, v, f1, f2, i;
LL ans;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
init(n);
ans=0;
for(i=0;i<n-1;i++){
scanf("%d%d%d",&fei[i].u,&fei[i].v,&fei[i].w);
ans+=(LL)fei[i].w;
}
for(i=0;i<k;i++){
scanf("%d",&u);
ha[u]=1;
}
sort(fei,fei+n-1);
for(i=0;i<n-1;i++){
f1=find1(bin[fei[i].u]);
f2=find1(bin[fei[i].v]);
if(!ha[f1]||!ha[f2]){
ans-=(LL)fei[i].w;
}
bin[f2]=f1;
ha[f1]+=ha[f2];
}
printf("%I64d\n",ans);
}
return 0;
}