构造完全图

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1081 字

Kruskal合并统计，非树边取w+1最省

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1489
// 题意：给定一棵树 T，求边权和最小的完全图 G，使得 T 是 G 唯一的最小生成树。
// 思路：按边权从小到大做 Kruskal，每次用一条树边合并大小为 a、b 的两块，这两块之间其余 a*b-1 条边必须严格大于它，取 w+1 最省。
// 复杂度：O(N log N) 时间 / O(N) 空间
// 易错点：答案可达 1e15 量级必须全程 long long；一定要先用旧的 a、b 算完贡献再做合并，顺序颠倒结果就错。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Edge{
    int u, v;
    long long w;
};
Edge e[MAXN];
int fa[MAXN];
long long sz[MAXN];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(){
    int n;
    if(!(cin >> n)) return 0;
    for(int i = 1; i <= n; i++){
        fa[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= n - 1; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + n, [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    long long ans = 0;
    for(int i = 1; i <= n - 1; i++){
        int a = find(e[i].u);
        int b = find(e[i].v);
        if(a == b) continue;
        ans += e[i].w + (sz[a] * sz[b] - 1) * (e[i].w + 1);
        fa[a] = b;
        sz[b] += sz[a];
    }
    cout << ans << '\n';
    return 0;
}

构造完全图

正文

一本通·提高篇的其它内容