loj#10067 构造完全图(最小生成树)

题目

解析

和kruscal类似，我们要构造一个完全图，考虑往这颗最小生成树里加边

我们先把每一条边存下来，把两个端点分别放在不同的集合内，记录每个集合的大小，然后做kruscal，集合之间两两构造完全图，即两两合并，直到合并成为一个集合。

因为本来就有一条边相连，又要满足这条边的边权是最小的，显然合并两个集合的代价是\((size[x]*size[y]-1)*(w[i]+1)\)，然后\(f[x]=y\)，最后再加上原来这棵树的总权值就好了

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, num, ans;

int size[N], fa[N];

struct node {

    int u, v, w;

    bool operator<(const node &oth) const { return w < oth.w; }

} e[N];

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

signed main() {

    cin >> n;

    for (int i = 1, x, y, z; i < n; ++i) {

        cin >> x >> y >> z;

        e[++num] = (node){ x, y, z };

    }

    sort(e + 1, e + 1 + num);

    for (int i = 1; i <= n; ++i) fa[i] = i, size[i] = 1;

    for (int i = 1; i <= num; ++i) {

        int x = find(e[i].u), y = find(e[i].v);

        if (x == y) continue;

        ans += (size[x] * size[y] - 1) * (e[i].w + 1) + e[i].w;

        fa[x] = y, size[y] += size[x];

    }

    cout << ans;

}

巴特西

loj#10067 构造完全图(最小生成树)

题目

解析

代码

最新文章

热门文章