思路是找最大的不与敌方点相连(我方点不一定联通)的所有连边,然后总边权值-找到的边权值=删掉的最小边
好像是并查集的一些操作引起的,有问题的地方找到了,但不知道怎么解决:
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct Edge{
long long w,to,pre;
}edge[100100];
bool enemy[100100];
int fa[100100];
bool cmp(Edge a,Edge b)
{
return a.w>b.w;
}
long long find(int k)
{
if(fa[k]!=k)
fa[k]=find(k);
return fa[k];
}
int main()
{
cin>>n>>k;
long long total=0;
for(int i=0;i<k;i++)
{
int t;
cin>>t;
enemy[t]=1;
}
for(int i=0;i<n;i++)
fa[i]=i;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
edge[i].pre=a;
edge[i].to=b;
edge[i].w=c;
total+=c;
}
sort(edge,edge+n-1,cmp);
long long ans=0;
for(int i=0;i<n-1;i++)
{
bool A,B;
A=enemy[find(edge[i].pre)];
B=enemy[find(edge[i].to)];
//这段以下有问题
if(!A||!B)
{
if(A&&!B)
fa[find(edge[i].to)]=find(edge[i].pre);
else if(B&&!A)
fa[find(edge[i].pre)]=find(edge[i].to);
ans+=edge[i].w;
}
//这段以上有问题
}
cout<<total-ans;
return 0;
}