Solves

Author: lllyouo
Date: 20250309
tag: 次小生成树
link: https://www.luogu.com.cn/problem/P4180

问题描述

link

分析

次小生成树分为两种：

非严格次小生成树：边权和最小的满足边权和大于等于最小生成树边权和的生成树。
严格次小生成树：边权和最小的满足边权和严格大于最小生成树边权和的生成树。

求解方法：

求解次小生成树有两种方法：

先求出最小生成树，然后再枚举删除最小生成树中的一条边，再求一次最小生成树，取最小值即可。
先求出最小生成树，然后再枚举所有非树边插入到最小生成树中，此时会形成一个环，删除环中权值最大的边之后得到的生成树是一个可行的解，取最小值即可。

上述算法中，方法 $1$ 只适合于求解非严格次小生成树，而方法 $2$ 既可以求解非严格次小生成树也可以求解严格次小生成树。

参考代码

样例输入

样例输出

非严格次小生成树

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
struct Edge {
    int u, v, w;

    bool operator< (const Edge& x) {
        return w < x.w;
    }
};
vector<Edge> e;
int n, m, p[N], vis[N];

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

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        e.push_back({a, b, c});
    }
    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) p[i] = i;

    long long ans = 1e18, tot = 0, cnt = 0;
    for (int i = 0; i < e.size(); i++) {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if (fu != fv) {
            tot += e[i].w;
            vis[cnt++] = i;
            p[fu] = fv;
        }
    }

    for (int i = 0; i < n- 1; i++) {
        for (int j = 1; j <= n; j++) p[j] = j;

        long long tmp = 0, c = 0;
        for (int j = 0; j < e.size(); j++) {
            if (j == vis[i]) continue;

            int fu = find(e[j].u);
            int fv = find(e[j].v);
            if (fu != fv) {
                tmp += e[j].w;
                c++;
                p[fu] = fv;
            }
        }
        if (c == n - 1 && tot != tmp) ans = min(ans, tmp);
    }
    cout << ans << endl;

    return 0;
}

严格次小生成树

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 510, M = 2 * N;
struct Edge {
    int u, v, w, flag;

    bool operator< (const Edge& x) {
        return w < x.w;
    }
};
vector<Edge> edges;
int n, m, p[N], vis[N];
int h[N], e[M], w[M], ne[M], idx;
int dis1[N][N], dis2[N][N];

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

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

void dfs(int u, int fu, int v1, int v2, int d1[], int d2[]) {
    d1[u] = v1, d2[u] = v2;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j != fu) {
            int tv1 = v1, tv2 = v2;
            if (w[i] > tv1) tv2 = tv1, tv1 = w[i];
            else if (w[i] < tv1 && w[i] > tv2) tv2 = w[i];
            dfs(j, u, tv1, tv2, d1, d2);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        edges.push_back({a, b, c});
    }
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++) p[i] = i;
    memset(h, -1, sizeof h);

    long long tot = 0;
    for (int i = 0; i < edges.size(); i++) {
        int fu = find(edges[i].u);
        int fv = find(edges[i].v);
        if (fu != fv) {
            tot += edges[i].w;
            edges[i].flag = true;
            add(edges[i].u, edges[i].v, edges[i].w);
            add(edges[i].v, edges[i].u, edges[i].w);
            p[fu] = fv;
        }
    }

    for (int i = 1; i <= n; i++) dfs(i, -1, -1e9, -1e9, dis1[i], dis2[i]);

    long long ans = 1e18;
    for (int i = 0; i < m; i++) {
        if (!edges[i].flag) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            long long t = 0;
            if (w > dis1[u][v]) t = tot + w - dis1[u][v];
            else if (w > dis2[u][v]) t = tot + w - dis2[u][v];
            ans = min(ans, t);
        }
    }
    cout << ans << endl;

    return 0;
}

注意

以上两份示例代码都无法过该题！如何维护环上边权的最大值呢？倍增、LCA

问题描述 ​

分析 ​

参考代码 ​

非严格次小生成树 ​

严格次小生成树 ​

注意 ​

问题描述

分析

参考代码

非严格次小生成树

严格次小生成树

注意