蒟蒻30pts求助
查看原帖
蒟蒻30pts求助
260978
Day_Dreamer_H楼主2021/12/29 19:30

对了1,3,4三个点,其他全WA

#include<bits/stdc++.h>
using namespace std;
struct edge {
	int u,v,w;
}a[100005];
long long n,k,sum,maximum;
bool occupy[100005];
int fa[100005],son[100005];
bool cmp(edge a1,edge a2){
	if(a1.w>a2.w)return true;
	else return false;
}
void DFS(int now,int last){
	if(occupy[now])return ;
	occupy[now] = true;
//	cout<<now<<" "<<last<<" "<<fa[now]<<" "<<son[now]<<endl;
	if(last == fa[now]&&!occupy[son[now]]&&son[now]!=-1){
		DFS(son[now],now);
	}
	if(last == son[now]&&!occupy[fa[now]]&&fa[now]!=-1){
		DFS(fa[now],now);
	}
}
int main(){
	memset(fa,-1,sizeof(fa));
	memset(son,-1,sizeof(son));
	cin>>n>>k;
	for(int i = 0;i<k;i++){
		int x;
		cin>>x;
		occupy[x] = true;
	}
	for(int i = 0;i<n-1;i++){
		cin>>a[i].u>>a[i].v>>a[i].w;
		sum+=a[i].w;
	}
	sort(a,a+n-1,cmp);
	for(int i = 0;i<n-1;i++){
//		cout<<"occupy:";
//		for(int j = 0;j<n;j++)if(occupy[j])cout<<j<<" ";
//		cout<<endl;
		if(occupy[a[i].u]&&occupy[a[i].v])continue;
		fa[a[i].v] = a[i].u;
		son[a[i].u] = a[i].v; 
//		cout<<endl<<"DFS:"<<endl;
		if(occupy[a[i].u]){
			DFS(a[i].v,a[i].u);
		}
		if(occupy[a[i].v]){
			DFS(a[i].u,a[i].v);
		}
//		cout<<endl<<"DFS end"<<endl;
		maximum+=a[i].w;
//		cout<<"add:"<<a[i].u<<" "<<a[i].v<<endl;
	}
	cout<<sum-maximum;
} 
2021/12/29 19:30
加载中...