次小生成树

· · 个人记录

有意思的题QwQ 写一下博客QwQ

P4180\ [BJWC2010] 严格次小生成树

题目描述

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

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

对于次小生成树，我们知道它就是最小生成树噶掉一个边再加上一个边。枚举加上的这个边。 这里有个图，图上的是最小生成树，我们枚举边枚举到(2,4)，根据树的性质，点2和点4之前就有一条路径了，为了维护树的形状，我们要噶掉路径上最大的边。当然啦，如果我们噶掉的边跟接上的边权重一样，那么就不是严格次小生成树了。所以，这个时候我们要噶掉路径上次大的边，对于这个东西可以用树剖或者倍增之类的搞，我这里用的树剖QwQ

code:

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int inf = 11451419198101919;
bool used[314514];
int read() {
    int x = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (c^48),c = getchar();
    return x*f;
}
int pa[314514],n,m;
struct edge {
    int u,v,w;
    bool operator<(edge b) const {
        return w < b.w;
    }
}edges[311541];
int head[314514],nxt[311541],wei[311541],to[311541],cnt,crom;
void add(int u,int v,int w) {
    cnt++;
    wei[cnt] = w;
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
int find(int k) {
    if(pa[k] == k) return k;
    return (pa[k] = find(pa[k]));
}
int kruskal() {
    int num = 0;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        pa[i] = i;
    }
    sort(edges+1,edges+m+1);
    for(int i = 1; i <= m; i++) {
        int x = find(edges[i].u);
        int y = find(edges[i].v);
        int w = edges[i].w;
        if(x == y) continue;
        pa[x] = y,ans += w,used[i] = 1;
        add(edges[i].u,edges[i].v,w);
        add(edges[i].v,edges[i].u,w);
        if(++num == n-1) {
            break;
        }
    }
    return ans;
}
//krust

int dip[314514],jntm[314514],smg[314514],ikun[314514],siz[314514],child[314514],father[314514],top[314514],tot = 0;
void dfs(int now,int pa) {
    siz[now] = 1;
    father[now] = pa;
    dip[now] = dip[pa]+1;
    for(int i = head[now]; i; i = nxt[i]) {
        if(to[i] == pa) continue;
        dfs(to[i],now);
        siz[now] += siz[to[i]];
        jntm[to[i]] = wei[i];
        if(siz[to[i]] > siz[child[now]]) child[now] = to[i];
    }
}
void dfs2(int now,int tp) {
    top[now] = tp;
    smg[now] = ++tot;
    ikun[smg[now]] = jntm[now];
    if(!child[now]) return;
    dfs2(child[now],tp);
    for(int i = head[now]; i; i = nxt[i]) {
        if(to[i] != father[now] && to[i] != child[now]) {
            dfs2(to[i],to[i]);
        }
    }
}
int cmp(int a,int b) {return a>b;}
int treeb[314514],trees[314514];
int max2(int a,int b,int c,int d) {
    int cop[4];
    cop[0] = a;
    cop[1] = b;
    cop[2] = c;
    cop[3] = d;
    sort(cop,cop+4,cmp);
    for(int i = 1; i < 3; i++) {
        if(cop[i] != cop[0]) {
            return cop[i];
        }
    }
    return cop[0];
}
void build(int k = 1,int l = 1,int r = n) {
    if(l == r) {
        treeb[k] = ikun[l];
        return ;
    }
    int mid = (l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    treeb[k] = max(treeb[k<<1],treeb[k<<1|1]);
    trees[k] = max2(treeb[k<<1],trees[k<<1],treeb[k<<1|1],trees[k<<1|1]);
}
pair<int,int> query(int x,int y,int k = 1,int l = 1,int r = n) {
    if(x <= l && r <= y) return make_pair(treeb[k],trees[k]);
    if(y < l || r < x) return make_pair(-inf,-inf);
    int mid = (l+r)>>1;
    pair<int,int> p1 = query(x,y,k<<1,l,mid),p2 = query(x,y,k<<1|1,mid+1,r);
    return make_pair(max(p1.first,p2.first),max2(p1.first,p2.first,p1.second,p2.second));
}
int chop(int u,int v,int w) {
    int mx = -inf;
    while(top[u] != top[v]) {
        if(dip[top[u]] < dip[top[v]]) swap(u,v);
        pair<int,int> p = query(smg[top[u]],smg[u]);
        u = father[top[u]];
        mx = max(mx,(p.first == w)?p.second:p.first);
    }
    if(dip[u] < dip[v]) swap(u,v);
    pair<int,int> p = query(smg[v]+1,smg[u]);
    return max(mx,(p.first == w)?p.second:p.first);
}
//"deep cuts"

signed main() {
    n = read();
    m = read();
    for(int i = 1; i <= m; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        edges[i].u = u;
        edges[i].v = v;
        edges[i].w = w;
    }
    int cns = kruskal();
    dfs(1,0);
    dfs2(1,1);
    build(1,1,n);
    int ans = inf;
    for(int i = 1; i <= m; i++) {
        if(!used[i]) {
            int tmp = cns+edges[i].w-chop(edges[i].u,edges[i].v,edges[i].w);
            //cout << tmp << endl;
            if(ans > tmp && tmp != cns + edges[i].w && tmp > cns) ans = tmp;
        }
    }
    cout << ans;
    return 0;
}