BZOJ 1977 - [BeiJing2010组队]次小生成树 Tree

#图论 #生成树 #树链剖分 #RMQ

Published on 2016-08-10

描述

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。
正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：
如果最小生成树选择的边集是 $E_m$ ，严格次小生成树选择的边集是 $E_s$ ，那么需要满足（ $\mathrm{value}(e)$ 表示边 $e$ 的权值）：

\sum\mathrm{value}(e)(e\in E_m) < \sum\mathrm{value}(e)(e\in E_s)

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

分析

如果是求不严格的最小生成树，那么我们先求出最小生成树权值 $M$ ，对于每条未被选中的边 $(u, v, w)$ ，找到最小生成树上 $u\rightarrow v$ 路径上的最大值 $V$ ，那么新的生成树的权值是 $M - V + w$ 。找到 $M - V + w$ 的最小值即可。可用最小生成树的回路性质证明其正确性。

然而这题求的不严格的最小生成树，如果对于 $(u, v, w)$ 来说， $V = w$ ，那么总权值不变，等于这条边不能对答案产生贡献，这时需要找到这条路径上的严格次小边权 $V'$ ，则新的生成树的权值为 $M - V' + w$ 。
维护路径最大和严格次大值，可以使用树剖 + ST表，也可以使用树上倍增。
复杂度： $O(m\log n)$ 。

代码

//  Created by Sengxian on 7/21/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1977 树链剖分
# pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3, maxm = 300000 + 3;
struct edge {
    int from, to, cost;
    edge(int from, int to, int cost): from(from), to(to), cost(cost) {}
    edge() {}
    inline bool operator < (const edge &ano) const {
        return cost < ano.cost;
    }
}edges[maxm];
int n, m, fa[maxn];
bool choose[maxn];

namespace union_find_set {
    inline int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline void unite(int x, int y) {
        x = find(x), y = find(y);
        fa[x] = y;
    }
    inline bool same(int x, int y) {
        return find(x) == find(y);
    }
}

int depth[maxn], dfn[maxn], bel[maxn], fv[maxn];
namespace heavy_light_decomposition {
    struct edge {
        edge *next;
        int to, cost;
        edge(edge *next, int to, int cost): next(next), to(to), cost(cost) {}
        edge() {}
    }*first[maxn], pool[maxn * 2];
    vector<edge> G[maxn];
    int tsp = 0, s[maxn];
    inline void addEdge(int f, int t, int c) {
        static edge *pit = NULL;
        if (pit == NULL) pit = pool;
        first[f] = new(pit++) edge(first[f], t, c);
        first[t] = new(pit++) edge(first[t], f, c);
    }
    int dfs1(int u, int fa) {
        ::fa[u] = fa, depth[u] = fa == -1 ? 0 : depth[fa] + 1;
        s[u] = 1;
        for (edge *e = first[u]; e; e = e->next)
            if (e->to != fa) fv[e->to] = e->cost, s[u] += dfs1(e->to, u);
        return s[u];
    }
    void dfs2(int u, int num) {
        bel[u] = num, dfn[u] = tsp++;
        int idx, Max = 0;
        for (edge *e = first[u]; e; e = e->next)
            if (e->to != fa[u] && s[e->to] > Max) Max = s[idx = e->to];
        if (Max == 0) return;
        dfs2(idx, num);
        for (edge *e = first[u]; e; e = e->next)
            if (e->to != fa[u] && e->to != idx) dfs2(e->to, e->to);
    }
    inline void decomposition() {
        tsp = 0;
        dfs1(0, -1), dfs2(0, 0);
    }
}

#define HLD heavy_light_decomposition

struct state {
    int max, max2;
    state(int max, int max2): max(max), max2(max2) {}
    state(): max(-1), max2(-1) {}
}maxVal[17][maxn];

inline state max(const state &lhs, const state &rhs) {
    state s = state(max(lhs.max, rhs.max), max(lhs.max2, rhs.max2));
    if (lhs.max != rhs.max) s.max2 = max(s.max2, min(lhs.max, rhs.max));
    return s;
}

inline void process() {
    for (int i = 0; i < n; ++i) maxVal[0][dfn[i]] = state(fv[i], -1);
    for (int w = 1; (1 << w) <= n; ++w)
        for (int i = 0; i + (1 << w) <= n; ++i)
            maxVal[w][i] = max(maxVal[w - 1][i], maxVal[w - 1][i + (1 << (w - 1))]);
}

int logs[maxn];
inline state queryMax(int l, int r) {
    if (l >= r) return state(-1, -1);
    static int bit;
    bit = logs[r - l];
    return max(maxVal[bit][l], maxVal[bit][r - (1 << bit)]);
}

inline state query(int x, int y) {
    state ans = state(-1, -1);
    while (bel[x] != bel[y]) {
        if (depth[bel[x]] < depth[bel[y]]) swap(x, y);
        ans = max(ans, queryMax(dfn[bel[x]], dfn[x] + 1));
        x = fa[bel[x]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    ans = max(ans, queryMax(dfn[x] + 1, dfn[y] + 1));
    return ans;
}

inline ll minimum_spanning_tree() {
    sort(edges, edges + m);
    for (int i = 0; i < n; ++i) fa[i] = i;
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
        using namespace union_find_set;
        if (!same(edges[i].from, edges[i].to)) {
            choose[i] = true;
            unite(edges[i].from, edges[i].to);
            HLD::addEdge(edges[i].from, edges[i].to, edges[i].cost);
            res += edges[i].cost;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    return res;
}

int main() {
    logs[0] = logs[1] = 0;
    for (int i = 2; i < maxn; ++i) logs[i] = logs[i >> 1] + 1;
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < m; ++i)
        edges[i].from = ReadInt() - 1, edges[i].to = ReadInt() - 1, edges[i].cost = ReadInt();
    ll res = minimum_spanning_tree();
    HLD::decomposition();
    process();
    ll ans = 1LL << 60, tmp;
    for (int i = 0; i < m; ++i) if (choose[i] == false) {
        tmp = res + edges[i].cost;
        state ret = query(edges[i].from, edges[i].to);
        if (ret.max == edges[i].cost) tmp -= ret.max2;
        else tmp -= ret.max;
        if (tmp > res) ans = min(ans, tmp); 
    }
    printf("%lld\n", ans);
    return 0;
}

Codeforces 704B - Ant Man HDOJ 5808 - Price List Strike Back

Sengxian's Blog

BZOJ 1977 - [BeiJing2010组队]次小生成树 Tree

描述

分析

代码