次小生成树

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 3547 字
树上倍增维护路径最大与次大边求次小生成树
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1493
// 题意：N 点 M 边无向图，求严格次小生成树的边权和，即边权和严格大于最小生成树的最小生成树。
// 思路：Kruskal 建最小生成树，树上倍增预处理每段路径的最大边与严格次大边，枚举非树边替换路径上最大或次大边取最小增量。
// 复杂度：O(M log M + M log N) 时间 / O(N log N + M) 空间
// 易错点：非树边权等于路径最大边时只能替换严格次大边，否则得到的仍是最小生成树；倍增合并两段时要重新取前两大值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 300005;
const int LOG = 18;
const long long INF = (1LL << 60);
struct Edge{
    int u, v;
    long long w;
    bool used;
};
Edge e[MAXM];
int fa[MAXN];
int dep[MAXN];
int up[LOG][MAXN];
long long m1[LOG][MAXN];
long long m2[LOG][MAXN];
vector<pair<int, long long>> adj[MAXN];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void take2(long long &r1, long long &r2, long long x){
    if(x > r1){
        r2 = r1;
        r1 = x;
    }
    else if(x > r2){
        r2 = x;
    }
}
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].used = false;
    }
    sort(e, e + m, [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    for(int i = 1; i <= n; i++) fa[i] = i;
    long long sum = 0;
    for(int i = 0; i < m; i++){
        int a = find(e[i].u);
        int b = find(e[i].v);
        if(a == b) continue;
        fa[a] = b;
        e[i].used = true;
        sum += e[i].w;
        adj[e[i].u].push_back({e[i].v, e[i].w});
        adj[e[i].v].push_back({e[i].u, e[i].w});
    }
    queue<int> q;
    dep[1] = 0;
    up[0][1] = 0;
    m1[0][1] = -1;
    m2[0][1] = -1;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(size_t i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].first;
            long long w = adj[u][i].second;
            if(v == up[0][u]) continue;
            up[0][v] = u;
            m1[0][v] = w;
            m2[0][v] = -1;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
    for(int k = 1; k < LOG; k++){
        for(int v = 1; v <= n; v++){
            int mid = up[k - 1][v];
            up[k][v] = up[k - 1][mid];
            m1[k][v] = m1[k - 1][v];
            m2[k][v] = m2[k - 1][v];
            take2(m1[k][v], m2[k][v], m1[k - 1][mid]);
            take2(m1[k][v], m2[k][v], m2[k - 1][mid]);
        }
    }
    long long ans = INF;
    for(int i = 0; i < m; i++){
        if(e[i].used) continue;
        int u = e[i].u;
        int v = e[i].v;
        long long w = e[i].w;
        long long r1 = -1, r2 = -1;
        if(dep[u] < dep[v]) swap(u, v);
        int diff = dep[u] - dep[v];
        for(int k = 0; k < LOG; k++){
            if((diff >> k) & 1){
                take2(r1, r2, m1[k][u]);
                take2(r1, r2, m2[k][u]);
                u = up[k][u];
            }
        }
        if(u != v){
            for(int k = LOG - 1; k >= 0; k--){
                if(up[k][u] != up[k][v]){
                    take2(r1, r2, m1[k][u]);
                    take2(r1, r2, m2[k][u]);
                    take2(r1, r2, m1[k][v]);
                    take2(r1, r2, m2[k][v]);
                    u = up[k][u];
                    v = up[k][v];
                }
            }
            take2(r1, r2, m1[0][u]);
            take2(r1, r2, m2[0][u]);
            take2(r1, r2, m1[0][v]);
            take2(r1, r2, m2[0][v]);
        }
        if(w > r1){
            ans = min(ans, sum - r1 + w);
        }
        else if(r2 >= 0 && w > r2){
            ans = min(ans, sum - r2 + w);
        }
    }
    cout << ans << '\n';
    return 0;
}
次小生成树

正文

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