10%..
  • 板块P2700 逐个击破
  • 楼主yu_666
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/11 16:05
  • 上次更新2023/11/11 18:11:41
查看原帖
10%..
317399
yu_666楼主2023/11/11 16:05
#include<iostream>
#include<algorithm>
using namespace std;
struct Edge
{
	int x,y,w;
 }e[100005];
 int father[100005],ans,ki,flag[100005];long long mst;
 bool cmp(Edge x,Edge y){
 	return x.w<y.w;
 }
 int getFather(int u){
 	if(father[u]==u) return u;
 	return father[u]=getFather(father[u]);
 }
int main()
{
	int n,m,x,y,k;
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>ki;
		flag[ki]=1;
	}
	for(int i=1;i<=n-1;i++)
		cin>>e[i].x>>e[i].y>>e[i].w;
	sort(e+1,e+n,cmp);
	for(int i=1;i<=n;i++)
		father[i]=i;
	for(int i=1;i<=n-1;i++)
	{
		x=getFather(e[i].x);
		y=getFather(e[i].y);
		if(flag[x]&&flag[y]){
			mst+=e[i].w;
			ans++;
			if(ans==k-1) break;
		}
		else {
			if(flag[x])
				father[y]=x;
			else
				father[x]=y;
		}
	}
	cout<<mst<<endl;
	return 0;
}
2023/11/11 16:05
加载中...