WA声一片,求调
查看原帖
WA声一片,求调
794148
cyx20091026楼主2024/12/7 08:28
#include<bits/stdc++.h>
using namespace std;
int n,k;
int ans=0;
struct Edge{
	int ui,vi,wi;
	bool operator < (const Edge b)const{
		return b.wi<wi;
	}
}edge[100001];
bool vis[100001];
int fa[100001];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
	cin>>n>>k;
	for(int i=0;i<=n-1;i++){
		fa[i]=i;
	}
	int ui,vi,wi;
	int x;
	for(int i=1;i<=k;i++){
		cin>>x;
		vis[x]=true;
	}
	for(int i=1;i<=n-1;i++){
		cin>>ui>>vi>>wi;
		edge[i]={ui,vi,wi};
		ans+=wi;
	}
	sort(edge+1,edge+n);
	for(int i=1;i<=n-1;i++){
		int eu=fa[edge[i].ui];
		int ev=fa[edge[i].vi];
		if(vis[eu]&&vis[ev]) continue;
		vis[eu]=(vis[eu]||vis[ev]);
		fa[ev]=eu;
		ans-=edge[i].wi;
	}
	cout<<ans;
	return 0;
}

20分QAQ

2024/12/7 08:28
加载中...