算法竞赛进阶指南.次小生成树

题目

356. 次小生成树

算法标签: $Kruskal$, $MST$, 倍增优化, $lca$

思路

因为要求的是严格次小生成树, 假设最小生成树的和为$s$, 遍历每一个非树边$e$, 那么最后答案就是$\min (s+e.w-v)$, $v$是当前非树边的路径上最长的边
如果最长边是最小生成树的边, 使用次长边, 因此需要处理两个数组$d1$, $d2$分别代表最长边和次长边, 算法时间复杂度$O(E\log E)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 6e5 + 10, K = 18;
const int INF = 0x3f3f3f3f;

int n, m;
struct Edge {
   
    int u, v, w;
    bool is_tr = false;
    bool operator< (const Edge &e) const {
   
        return w < e.w;
    }
} edges[M];
int head[N], ed[N << 1], ne[N << 1], w[N << 1], idx;
int fa[N][K], depth[N];
int d1[N][K], d2[N][K];
int p[N];

int find(int x) {
   
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

LL kruskal() {
   
    sort(edges, edges + m);
    for (int i = 0; i <= n; ++i) p[i] = i;
    LL res = 0;
    for (int i = 0; i < m; ++i) {
   
        auto &[u, v, w, is_tr] = edges[i];
        int fa1 = find(u), fa2 = find(v);
        if (fa1 == fa2) continue;
        res += w;
        p[fa2] = fa1;
        is_tr = true;
        add(u, v, w), add(v, u, w);
    }
    return res;
}

void bfs() {
   
    int q[N], h = 0, t = -1;
    q[++t] = 1;
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;

    while (h <= t) {
   
        int u = q[h++];
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (depth[u] + 1 < depth[v]) {
   
                depth[v] = depth[u] + 1;
                q[++t] = v;

                fa[v][0] = u;
                d1[v][0] = w[i];
                d2[v][0] = -INF;
                for (int k = 1; k < K; ++k) {
   
                    int mid = fa[v][k - 1];
                    fa[v][k] = fa[mid][k - 1];

                    int arr[4] = {
   
                            d1[v][k - 1],
                            d2[v][k - 1],
                            d1[mid][k - 1],
                            d2[mid][k - 1]
                    };

                    int val1 = -INF, val2 = -INF;
                    for (int j = 0; j < 4; ++j) {
   
                        if (arr[j] > val1) val2 = val1, val1 = arr[j];
                        else if (arr[j] > val2 && arr[j] < val1) val2 = arr[j];
                    }
                    d1[v][k] = val1;
                    d2[v][k] = val2;
                }
            }
        }
    }
}

int lca(int u, int v, int val) {
   
    if (depth[u] < depth[v]) swap(u, v);
    vector<int> vec;

    for (int k = K - 1; k >= 0; --k) {
   
        if (depth[fa[u][k]] >= depth[v]) {
   
            vec.push_back(d1[u][k]);
            vec.push_back(d2[u][k]);
            u = fa[u][k];
        }
    }

    if (u != v) {
   
        for (int k = K - 1; k >= 0; --k) {
   
            if (fa[u][k] != fa[v][k]) {
   
                vec.push_back(d1[u][k]);
                vec.push_back(d2[u][k]);
                vec.push_back(d1[v][k]);
                vec.push_back(d2[v][k]);
                u = fa[u][k], v = fa[v][k];
            }
        }
        vec.push_back(d1[u][0]);
        vec.push_back(d2[u][0]);
        vec.push_back(d1[v][0]);
        vec.push_back(d2[v][0]);
    }

    int val1 = -INF, val2 = -INF;
    for (int t : vec) {
   
        if (t > val1) val2 = val1, val1 = t;
        else if (t > val2) val2 = t;
    }

    if (val1 < val) return val1;
    if (val1 == val) return val2;
    return -INF;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {
   u, v, w};
    }

    LL sum = kruskal();
    bfs();

    LL ans = 1e18;
    for (int i = 0; i < m; ++i) {
   
        auto &[u, v, w, is_tr] = edges[i];
        if (is_tr) continue;
        ans = min(ans, sum + w - lca(u, v, w));
    }

    cout << ans << "\n";
    return 0;
}

*警示后人

因为求的是严格次小生成树, 因此在计算的时候不是arr[j] > val2而是arr[j] > val2 && arr[j] < val1, 否则求出的就不是严格的了