BZOJ1977: [BeiJing2010组队]次小生成树 Tree

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

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 3446 Solved: 915
[Submit][Status][Discuss]

Description

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值) 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

Output

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

Sample Input

5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6

Sample Output

HINT

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

Source

这道题最猥琐的地方在于严格次小。思路大概是先做最小生成树，然后再在树上倍增处理两点之间路过的边的最大权值和次大权值（因为要严格次小），最后枚举其他的每一条边，查询两点间在生成树上（到LCA）的路径经过的权值最大的边的边权（如果和当前枚举的边的边权相等，我们就需要次大边权）。每次都计算删去该边，加上当前枚举边后生成树的大小（保证了树的连通性），取最小值。代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 3e5 + 5;
const int max2 = 20;
const LL inf = 0x7fffffffffffffff;
struct edge {
    int u, v, w;
    bool operator < (const edge &a) const {
        return w < a.w;
    }
}es[maxm];
struct Edge {
    int v, w, next;
}e[maxn << 1];
int n, m;
int head[maxn], cnt;
int p[maxn][max2 + 3];
int mx[maxn][max2 + 3], smx[maxn][max2 + 3];
LL d[maxn], depth[maxn];
bool vis[maxm];
void adde(const int &u, const int &v, const int &w) {
    e[++cnt] = (Edge) {v, w, head[u]};
    head[u] = cnt;
}
namespace DSU {
    int fa[maxn];
    void init(int n) {For(i, 1, n) fa[i] = i;}
    int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
    void combine(int a, int b) {fa[find(a)] = find(b);}
}
void pre(int u, int fa, int w) {
    d[u] = d[fa] + w;
    depth[u] = depth[fa] + 1;
    p[u][0] = fa, mx[u][0] = w;
    for(register int i = 1; i <= max2; ++i) {
        p[u][i] = p[p[u][i - 1]][i - 1];
        mx[u][i] = max(mx[p[u][i - 1]][i - 1], mx[u][i - 1]);
        if(mx[u][i - 1] == mx[p[u][i - 1]][i - 1])
            smx[u][i] = max(smx[u][i - 1], smx[p[u][i - 1]][i - 1]);
        else {
            smx[u][i] = min(mx[u][i - 1], mx[p[u][i - 1]][i - 1]);
            smx[u][i] = max(smx[u][i - 1], smx[u][i]);
            smx[u][i] = max(smx[u][i], smx[p[u][i - 1]][i - 1]);
        }
    }
    for(register int i = head[u]; i; i = e[i].next)
        if(e[i].v != fa) pre(e[i].v, u, e[i].w);
}
int lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
    for(register int i = max2; i >= 0; --i) 
        if(depth[a] - (1 << i) >= depth[b]) 
            a = p[a][i];
    if(a == b) return a;
    for(register int i = max2; i >= 0; --i) 
        if(p[a][i] != p[b][i])
            a = p[a][i], b = p[b][i];
    return p[a][0];
}
int gmx(int a, int anc, int mx[maxn][max2 + 3]) {
    int m = 0;
    for(register int i = max2; i >= 0; --i) 
        if(depth[a] - (1 << i) >= depth[anc]) 
            m = max(m, mx[a][i]), a = p[a][i];
    return m;
}
bool cmp(const int &a, const int &b) {
    return a > b;
}
int main() {
    scanf("%d%d", &n, &m);
    For(i, 1, m) scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].w);
    sort(es + 1, es + m + 1), DSU::init(n);
    int u, v, sum = 0;
    LL wt = 0, ans = inf;
    For(i, 1, m) {
        u = es[i].u, v = es[i].v;
        if(DSU::find(u) == DSU::find(v))
            continue;
        vis[i] = 1;
        adde(u, v, es[i].w);
        adde(v, u, es[i].w);
        wt += es[i].w;
        DSU::combine(u, v), ++sum;
    }
    pre(1, 0, 0);
    For(i, 1, m) {
        int v = es[i].v, u = es[i].u, MX[4], dw;
        if(vis[i]) continue;
        int LCA = lca(u, v);
        MX[0] = gmx(u, LCA, mx);
        MX[1] = gmx(u, LCA, smx);
        MX[2] = gmx(v, LCA, mx);
        MX[3] = gmx(v, LCA, smx);
        sort(MX, MX + 4, cmp), dw = MX[0];
        if(es[i].w == dw) dw = MX[1];
        ans = min(ans, wt - dw + es[i].w);
    }
    printf("%lld", ans);
    return 0;
}

Rockdu's Blog