10分求调
查看原帖
10分求调
561949
syr1125楼主2024/5/7 21:30
#include <bits/stdc++.h>
using namespace std;

int a[500005];

struct edge
{
	int x, y, z;
	
	bool operator < (const edge __) const
	{
		return z > __.z;
	}
}edge[500005];

int find(int x)
{
	if (a[x] != x)
	{
		a[x] = find(a[x]);
	}
	return a[x];
}

int n, k, m, vis[500005];
int main()
{
	scanf("%d%d", &n, &k);
	m = n - 1;
	long long tot = 0;
	for (int i = 1; i <= k; i ++)
	{
		int x;
		scanf("%d", &x);
		vis[x] = x;
	}
	for (int i = 1; i <= m; i ++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		edge[i].x = x;
		edge[i].y = y;
		edge[i].z = z;
		tot += z;
	}	
	sort(edge + 1, edge + 1 + m);
	for (int i = 0; i <= n; i ++) 
	{
		a[i] = i;
	}
	
	long long res = 0, ans = 0;
	for (int i = 1; i <= m; i ++)
	{
		int _x = edge[i].x, _y = edge[i].y, _z = edge[i].z;
		if (!(vis[_x] && vis[_y]))
		{
			int a1 = find(_x), b1 = find(_y);
			if (a1 == b1)
			{
				continue;
			}
			a[a1] = b1;	
			ans += _z;
			if(vis[_x]) vis[_y] = 1;
        	else if (vis[_y]) vis[_x] = 1;
		}
	}
	printf("%lld", tot - ans);
	return 0;
}

2024/5/7 21:30
加载中...