次小生成树

Uuuuuur_ · 2023-08-01 13:49:36 · 题解

最小生成树很简单，略过。

重点是次小生成树，假设我们已经求出最小生成树 T，枚举每一条没有选进 T 的边 (u,v,w)，尝试把它加到生成树里，这时会发现树上出现了一个环，只用删掉原最小生成树上 u 和 v 路径上最长的边，就能得到一个可能的次小生成树。

简单来讲，就是用一条不在最小生成树的边替换掉一条尽可能长的树边，这条树边肯定在 u 到 v的路径上。

两点间最长路径，可以用 LCA 求解，当然这道题的数据范围直接暴力走也行。我的代码中使用了倍增的 LCA，复杂度 O(m \log m + m \log n)。

刚刚讲的都是非严格次小生成树，如果要严格，只要排除新加的边和替换的边相等这种情况就好了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int u, v, w;
    bool operator < (const edge &b) const {
        return w < b.w;
    }
};
struct node {
    int v, w;
};
const int N = 105;
const int H = 9;
const int inf = 0x3f3f3f3f3f3f3f3f;
int T;
int n, m;

vector<node> t[N];
edge e[N * N];
bool used[N * N];
int f[15][N];
int h[15][N];
int fa[N];
int dep[N];
int maxx, sec;
void init() {
    maxx = sec = 0;
    memset(f, 0, sizeof f);
    memset(h, 0, sizeof h);
    memset(dep, 0, sizeof dep);
    memset(used, 0, sizeof used);
    maxx = 0, sec = inf;
    memset(used, 0, sizeof used);
    for (int i = 0; i < N; i++) vector<node>().swap(t[i]);
    for (int i = 1; i <= n; i++) fa[i] = i;
}
int get(int x) {return x == fa[x] ? x : fa[x] = get(fa[x]);}
void merge(int x, int y) {
    int fx = get(x), fy = get(y);
    if (fx != fy) fa[fx] = fy; 
}

void dfs(int u, int fa, int d) {
    dep[u] = d;
    for (int i = 0; i < t[u].size(); i++) {
        int v = t[u][i].v, w = t[u][i].w;
        if (v != fa) {
            f[0][v] = u;
            h[0][v] = w;
            for (int k = 1; k <= H; k++) {
                f[k][v] = f[k - 1][f[k - 1][v]];
                h[k][v] = max(h[k - 1][v], h[k - 1][f[k - 1][v]]);
            }
            dfs(v, u, d + 1);
        }
    }
} 
int calc(int x, int y) {
    int ans = 0;
    if (dep[x] < dep[y]) swap(x, y);
    for (int k = H; k >= 0; k--) {
        if (dep[f[k][x]] >= dep[y]) {ans = max(ans, h[k][x]); x = f[k][x];}
    }
    if (x == y) return ans;
    for (int k = H; k >= 0; k--) {
        if (f[k][x] != f[k][y]) {
            ans = max(ans, max(h[k][x], h[k][y]));
            x = f[k][x], y = f[k][y];
        }
    }
    ans = max(ans, max(h[0][x], h[0][y]));
    return ans;
}

void kruskal() {
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; i++) {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if (get(u) != get(v)) {
            t[u].push_back({v, w});
            t[v].push_back({u, w});
            merge(u, v); 
            maxx += w;
            used[i] = 1;
        }
    }
    dfs(1, 0, 1);
    for (int i = 1; i <= m; i++) {
        if (!used[i]) {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            sec = min(sec, maxx - calc(u, v) + w);
        }
    }  
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        init();
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> u >> v>> w;
            e[i] = {u, v, w};
        }
        kruskal();
        cout << maxx << ' ' << sec << '\n';
    }
    return 0;
}