Author: lllyouo
Date: 20250226
tag: 最大生成树
link: https://www.luogu.com.cn/problem/P2700

问题描述

link

分析

简单来说本题即是求花费最小的代价，使得某些被标记的点之间不连通。花费最小的代价删除边等价于花费最大的代价建立边，最后剩下没有建立的边就是答案。

因此，我们按照边权从大到小做最小生成树算法，为了保证两个标记节点不连通，当并查集合并时，如果两个节点均为标记节点，则不合并，否则合并。合并之后，我们将未标记节点标记（染色），防止标记节点通过未标记节点连通。

最后输出总边权减去最小生成树算法求得的边权即可！

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Edge {
	int u, v, w;

	bool operator< (const Edge& x) {
		return w > x.w;
	}
};

vector<Edge> e;
int n, m, vis[N], p[N];
long long ans, s;

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

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int t; cin >> t;
		vis[t] = 1;
	}
	for (int i = 0; i < n - 1; i++) {
		int a, b, c; cin >> a >> b >> c;
		e.push_back({a, b, c});
		s += c;
	}

	sort(e.begin(), e.end());
	for (int i = 0; i < n; i++) p[i] = i;

	for (int i = 0; i < e.size(); i++) {
		int fu = find(e[i].u);
		int fv = find(e[i].v);

		if (vis[fu] && vis[fv]) continue;

		p[fu] = fv;
		ans += e[i].w;
		if (vis[fu]) vis[fv] = true;
		else if (vis[fv]) vis[fu] = true;
	}

	cout << s - ans << endl;

	return 0;
}