题解 P4180 【[Beijing2010组队]次小生成树Tree】

attack · 2018-02-21 21:56:47 · 题解

更好的阅读体验点这里

次小生成树

我们已经熟知了求最小生成树的方法，用kruskal,prim算法都可以搞

那么我们如何求次小生成树呢？

这里次小生成树的定义是

边权和严格大于最小生成树的边权和最小的生成树

求解方法

次小生成树嘛，肯定和最小生成树脱不了关系

那么我们首先求出最小生成树

接下来，一个比较显然的思路是

枚举每一条未加入最小生成树的边，加入最小生成树，同时在最小生成树中删除边权最大的边

如果你想到了这里并写出了代码，那么恭喜你

你在里成功还有一步之遥成功掉进坑里了

比如下面的例子

蓝边表示最小生成树中的边，黄边表示新加入的边

在这种情况下，如果仅仅记录最大值的话，得到的答案一定是错的所以我们还要记录严格小于最大值的最大值

当产生冲突的时候我们需要删除严格小于最大值的最大值

优化

但是这样效率太低了，每一次查询都是O(n)的

有没有更好的方法呢？

不要忘了，最小生成树它是一棵树呀

树的链上最大最小值操作，你想到了什么？

没错！树上倍增

我们在倍增的过程中记录下最大值和严格小于最大值的最大值

这样每次查询的复杂度就变成log(n)啦

总结

流程

整个算法的流程大概是

求出最小生成树
构造出倍增数组
每次树上倍增查询

时间复杂度

用kruskal是O(m\log m+Q\log (n))

用prim是O(n\log n+Q\log (n))

Q为询问次数

代码

放一道裸题

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define Pair pair<int, int> 
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second 
#define LL long long
using namespace std;
const int MAXN = 3e5 + 10;
const LL INF = 1e15 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
struct Edge {
    int u, v, w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
} E[MAXN];
vector<Pair> v[MAXN];
int N, M, fa[MAXN], vis[MAXN], dep[MAXN], f[MAXN][19], mx[MAXN][19], me[MAXN][19];;
LL sum;
int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void Kruskal() {
    sort(E + 1, E + M + 1);
    int tot = 0;
    for (int i = 1; i <= M; i++) {
        int x = E[i].u, y = E[i].v, fx = find(x), fy = find(y);
        if (fx != fy) {
            fa[fx] = fy; 
            tot++, sum += E[i].w, vis[i] = 1;
            v[x].push_back(MP(y, E[i].w)); 
            v[y].push_back(MP(x, E[i].w));
        }
        if (tot == N - 1) break;
    }
}
void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1; f[x][0] = fa; 
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i].fi) == fa) continue;
        mx[to][0] = v[x][i].se;
        dfs(to, x);
    }
}
void pre() {
    for (int i = 1; i <= 18; i++) {
        for (int j = 1; j <= N; j++) {
            f[j][i] = f[ f[j][i - 1] ][i - 1];
            int topf = f[j][i - 1];
            mx[j][i] = max(mx[j][i - 1], mx[topf][i - 1]);
            me[j][i] = max(me[j][i - 1], me[topf][i - 1]);
            if (mx[j][i - 1] > mx[topf][i - 1]) me[j][i] = max(me[j][i], mx[topf][i - 1]);
            else if (mx[j][i - 1] < mx[topf][i - 1]) me[j][i] = max(me[j][i], mx[j][i - 1]);
        }
    }
}
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 18; i >= 0; i--) if (dep[ f[x][i] ] >= dep[y] ) x = f[x][i];
    if (x == y) return x;
    for (int i = 18; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
int findmax(int x, int lca, int val) {
    LL ans = 0;
    for (int i = 18; i >= 0; i--) {
        if (dep[ f[x][i] ] >= dep[lca]) {
            if (mx[x][i] == val) ans = max(ans, (LL) me[x][i]);
            else ans = max(ans, (LL) mx[x][i]);
            x = f[x][i];
        }
    }
    return ans;
}
void work() {
    LL ans = INF;
    for (int i = 1; i <= M; i++) {
        if (vis[i]) continue;
        int x = E[i].u, y = E[i].v, z = E[i].w;
        int lca = LCA(x, y);
        int lmx = findmax(x, lca, z), rmx = findmax(y, lca, z);
        if (max(lmx, rmx) != z)  ans = min(ans, sum + z - max(lmx, rmx));
    }
    printf("%lld", ans);
}
int main() {
    N = read(), M = read();
    for (int i = 1; i <= N; i++) fa[i] = i;
    for (int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        E[i] = (Edge) {x, y, z};
    }
    Kruskal();
    dfs(1, 0);
    pre();
    work();
    return 0;
}