WA20pts大佬求调
  • 板块P2700 逐个击破
  • 楼主gjrBJ
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/26 20:17
  • 上次更新2025/1/27 09:34:45
查看原帖
WA20pts大佬求调
1350908
gjrBJ楼主2025/1/26 20:17

玄学,似乎输出0(

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Edge {
    int a, b, c;
}a[100010];
int n, m, k, cnt, ret, SUM, fa[1000010], z[1000010], ff[1000010];
int cmp(Edge x, Edge y) {
    return x.c > y.c;
}
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
signed main() {
    cin >> n >> k;
    m = n - 1;
    for (int i = 1; i <= k; i++) {
    	cin >> z[i];
    	ff[z[i]] = 1;
	}
    for (int i = 1; i <= m; i++) {
        cin >> a[i].a >> a[i].b >> a[i].c;
        SUM += a[i].c;
    }
    sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int t1 = find(a[i].a), t2 = find(a[i].b);
        if (t1 != t2 && (ff[a[i].a] == 0 || ff[a[i].b] == 0)) {
            fa[t1] = t2;
            cnt++;
            ret += a[i].c;
        }
    }
    cout << SUM-ret;
    return 0;
}
2025/1/26 20:17
加载中...