HDU 4313 Matrix(并查集/破坏边使得k个点两两不连通的最少代价)

HDU 4313 Matrix(并查集/破坏边使得k个点两两不连通的最少代价)

题目链接：
HDU 4313 Matrix
题意:
有 n $n$个点和n−1$n-1$条无向边，需要破坏一些边使得给定的 k $k$个点两两不连通，求最少的破坏代价？
数据范围:n≤105$n leq 10^5$
分析；

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int T, n, k, m;
int exist[MAX_N], father[MAX_N];struct Edge {int u, v, w;bool operator < (const Edge& rhs) const {return w > rhs.w;}
}edge[MAX_N];inline int find(int x)
{return father[x] == x ? x : father[x] = find(father[x]);
}ll solve()
{ll res = 0;for (int i = 0; i < m; ++i) {int u = edge[i].u, v = edge[i].v, w = edge[i].w;int fu = find(u), fv = find(v);if (exist[fu] && exist[fv] ) {res += w;father[fu] = fv;} else {if (exist[fu]) father[fv] = fu;else father[fu] = fv;}}return res;
}int main()
{scanf("%d", &T);while (T--) {scanf("%d%d", &n, &k);for (int i = 0; i < n - 1; ++i) {int u, v, w;scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);}for (int i = 0; i < n; ++i) { father[i] = i; }memset(exist, 0, sizeof(exist));for (int i = 0; i < k; ++i) {int id;scanf("%d", &id);exist[id] = 1;}m = n - 1;sort(edge, edge + m);printf("%lldn", solve());}return 0;
}