一、题意

输入一个n个点m条边的图，要求你计算出图中的最小生成树和次小生成树的权值和。

二、解析

最小生成树比较简单，直接上Kruskal算法模板即可。主要是次小生成树应该如何求解？

其实也比较简单，按照以下步骤即可：

  1. 求出最小生成树mst
  2. 通过以每个点为根分别进行dfs，得到maxW[maxn][maxn]数组。其中maxW[root][v]表示最小生成树mst上从root到v的路径上的最大的一条边的权值。
  3. 遍历所有不在mst上的边，比如为（u, v），用它去替换mst上从u到v路径上的最大边，从而得到一系列次小生成树替补。这些次小生成树替补权值和最小的那个就是次小生成树。

时间复杂度为O(n^2+mlogm)，基本够用了。

PS：原理简单，就是代码量较大...要维护一个存放边的容器E，同时还要维护一个存放最小生成树的边的容器mst。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 100 + 5, INF = 1 << 30;
struct edge {
    int u, v, w;
    bool flag = 0;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator < (const edge& rhs) const {
        return w < rhs.w;
    }
};
struct mst_edge {
    int v, w;
    mst_edge(int v, int w) : v(v), w(w) {}
};
vector<edge> E;
vector<mst_edge> mst[maxn];
int kase, n, m, Fa[maxn], maxW[maxn][maxn], ans1, ans2;

int find(int x) {
    return Fa[x] == x ? x : Fa[x] = find(Fa[x]);
}

void Kruskal() {
    for(int i = 1; i <= n; i ++) Fa[i] = i;
    sort(E.begin(), E.end());
    ans1 = 0;
    for(edge& e : E) {
        int u = find(e.u), v = find(e.v);
        if(u == v) continue;
        Fa[u] = v;
        ans1 += e.w;
        e.flag = 1;  // 标记这条边在mst中
        mst[e.u].push_back(mst_edge(e.v, e.w));  // 将最小生成树保存起来
        mst[e.v].push_back(mst_edge(e.u, e.w));
    }
}

void dfs(int root, int cur, int fa, int val) {  // 遍历最小生成树来生成maxW数组
    maxW[root][cur] = val;
    for(const mst_edge& e : mst[cur]) if(e.v != fa) {
        dfs(root, e.v, cur, max(val, e.w));
    }
}

void SKruskal() {
    Kruskal();
    for(int i = 1; i <= n; i ++) dfs(i, i, 0, 0);
    ans2 = INF;
    for(const edge& e : E) if(e.flag == 0) ans2 = min(ans2, ans1 - maxW[e.u][e.v] + e.w);
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> m;
        E.clear();
        for(int i = 1; i <= n; i ++) mst[i].clear();
        while(m --) {
            int u, v, w;
            cin >> u >> v >> w;
            E.push_back(edge(u, v, w));
        }
        SKruskal();
        cout << ans1 << " " << ans2 << endl;
    }
}

四、归纳

  • 次小生成树模板： 
struct edge {
    int u, v, w;
    bool flag = 0;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator < (const edge& rhs) const {
        return w < rhs.w;
    }
};
struct mst_edge {
    int v, w;
    mst_edge(int v, int w) : v(v), w(w) {}
};
vector<edge> E;  // 存放所有边的容器
vector<mst_edge> mst[maxn];  // 存放最小生成树的容器
int n, m, Fa[maxn], maxW[maxn][maxn], ans1, ans2;  // ans1, ans2分别为最小生成树和次小生成树的边权和

int find(int x) {
    return Fa[x] == x ? x : Fa[x] = find(Fa[x]);
}

void Kruskal() {
    for(int i = 1; i <= n; i ++) Fa[i] = i;
    sort(E.begin(), E.end());
    ans1 = 0;
    for(edge& e : E) {
        int u = find(e.u), v = find(e.v);
        if(u == v) continue;
        Fa[u] = v;
        ans1 += e.w;
        e.flag = 1;  // 标记这条边在mst中
        mst[e.u].push_back(mst_edge(e.v, e.w));  // 将最小生成树保存起来
        mst[e.v].push_back(mst_edge(e.u, e.w));
    }
}

void dfs(int root, int cur, int fa, int val) {  // 遍历最小生成树来生成maxW数组
    maxW[root][cur] = val;
    for(const mst_edge& e : mst[cur]) if(e.v != fa) {
        dfs(root, e.v, cur, max(val, e.w));
    }
}

void SKruskal() {
    Kruskal();  // 1. 求最小生成树mst
    for(int i = 1; i <= n; i ++) dfs(i, i, 0, 0);  // 2. 求maxW[root][v]数组
    ans = INF;
    for(const edge& e : E) if(e.flag == 0) ans2 = min(ans2, ans1 - maxW[e.u][e.v] + e.w);
    // 3. 用不在树上的边逐个替换，然后取最小的那个树就是次小生成树
}

int main() {
    ......
    SKruskal();
    ......
}
  • 虽然代码量大，不过只要思路清晰的话还是不容易错的