题解 P4180 【模板】严格次小生成树[BJWC2010]

题目描述

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

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。
输入输出格式
输入格式：

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

输出格式：

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

说明:
数据中无向图无自环;
$50%$ 的数据$N≤2000?M≤3000$;
$80%$的数据$N≤50000?M≤100000$;
$100%$ 的数据$N≤100000?M≤300000$;
边权值非负且不超过$10^9$ 。

基本思路：

先求出最小生成树，在建树时，将所有的边划分为两个集合（树边$E_T$和非树边$E_K$）
之后考虑将$\forall?e(u,v)\in E_K$分别加入到最小生成树上去，将树上$u,v$之间的最大边权$Maxvalue(u,v)$与$value(e)$作比较：

• 若$Maxvalue(u,v)\ne value(e)$ 则得到$MST^\prime$的一个候选值$MST-Maxvalue(u,v)+value(e)$
• 若$Maxvalue(u,v)= value(e)$ 则得到$MST^\prime$的一个候选值$MST-Maxvalue^\prime(u,v)+value(e)$
  （其中$MST^\prime$为次小生成树，$Maxvalue^\prime(u,v)$为树上$u,v$间的次大边权）

思路确定下来之后，最严峻的问题就是：如何快速求出$Maxvalue(u,v)$和$Maxvalue^\prime(u,v)$?

树上倍增$+LCA$

对所建立的最小生成树进行树上倍增，各元素意义如下：

• $f[?i?][?j?]$表示树上编号为$i$的点向上跳$2^j$步所到达的祖先编号
• $maxg[?i?][?j?]$表示树上编号为$i$的点以上长度为$2^j$的树上路径的最大边权值
• $ming[?i?][?j?]$表示树上编号为$i$的点以上长度为$2^j$的树上路径的次大边权值

在求处理树上路径$(u,v)$时先求出$LCA(u,v)$，再分为$(u,LCA(u,v))$和$(v,LCA(u,v))$两段处理，取两次答案的较大值作为当前的目标替换值（具体实现见代码中的$qmax$函数）

细节注意事项

个人来看，以下几点是非常重要滴：

1. $Kruskal$的构树（最基本的一步，千万不能出岔子）
2. 维护树上路径的边权最大值与次大值（重中之重！！！）
   千万要注意$maxg$和$ming$的转移,不然就有可能像我一样一直WA第一个点$...$
3. $LCA$辅助查询树上路径$(u,v)$之间的最大边权
   
4. 开$long?long$ 啊（不开$long?long$见祖宗$...$）

参考代码

下面是蒟蒻的代码（欢迎大佬来踩）

//由于本地调试的时候忘了开long long，所以所有的int都是long long...qwq
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
typedef long long LL;
const LL INF=2147483647000000;//INF 开大
// 空间都开大点
const LL MAXN=400010;
const LL MAXM=900010;
using namespace std;
inline LL read(){//读优
    LL s=0;bool f=false;char c=getchar();
    while(c<'0'||c>'9')f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return (f)?(-s):(s);
}
struct edge{
    LL u,v,w;bool bt;//bt为false则说明为非树边，为真则为树边
    void scan(){u=read(),v=read(),w=read();}
    bool operator<(const edge&obj)const{return w<obj.w;}
}e[MAXM];
LL tot,head[MAXN],nxt[MAXM<<1],v[MAXM<<1],w[MAXM<<1];
inline void Add_edge(LL from,LL to,LL dis){
    nxt[++tot]=head[from],head[from]=tot,v[tot]=to,w[tot]=dis;
}
LL fa[MAXN];
inline LL findd(LL k){
    return fa[k]==k?k:fa[k]=findd(fa[k]);
}
LL n,m,MST=0;
inline void kruskal(){
    for(LL i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+1+m);
    for(LL i=1;i<=m;i++){
        LL u=e[i].u;
        LL v=e[i].v;
        LL w=e[i].w;
        if(findd(u)!=findd(v)){
            MST+=w;
            e[i].bt=true;
            Add_edge(u,v,w);
            Add_edge(v,u,w);
            fa[findd(u)]=findd(v);
        }
    }
}
LL dep[MAXN],f[MAXN][19];
LL maxg[MAXN][19],ming[MAXN][19];
inline void dfs(LL u,LL p){
    for(LL i=1;i<=18;i++){
        f[u][i]=f[f[u][i-1]][i-1];
        maxg[u][i]=max(maxg[u][i-1],maxg[f[u][i-1]][i-1]);
        //maxg肯定为两段路径分别的maxg的较大值
        ming[u][i]=max(ming[u][i-1],ming[f[u][i-1]][i-1]);
        //先令ming为两段路径分别的ming的较大值
        //这个 if 非常重要！不然的话，要是边权最大的边有很多，就会使次大边权也为最大值
        if(maxg[u][i-1]!=maxg[f[u][i-1]][i-1])
            ming[u][i]=max(ming[u][i],min(maxg[u][i-1],maxg[f[u][i-1]][i-1]));
        //若两段的maxg相同，则不必要继续更新ming
        //否则要将ming与两段路径的maxg的较小值作比较，再次更新
    }
    for(LL i=head[u];i;i=nxt[i])
        if(!dep[v[i]]){
            f[v[i]][0]=u;
            maxg[v[i]][0]=w[i];
            ming[v[i]][0]=-INF;
            dep[v[i]]=dep[u]+1;
            dfs(v[i],u);
        }
}
inline LL LCA(LL x,LL y){
    if(dep[x]<dep[y]) swap(x,y);
    for(LL i=18;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(LL i=18;i>=0;i--)
        if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline LL qmax(LL x,LL y,LL z){
    LL ans=-INF;
    //ans记录树上(x,y)同一条链上的最大边权
    //由于主函数中求了LCA，所以在当前的函数中，y一定是x的祖先
    for(LL i=18;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]){
        //这个 if 的原理同上
        //若当前这条非树边的权与当前路径段的最大边权不等
            if(z!=maxg[x][i])
                //则用maxg更新一次
                ans=max(ans,maxg[x][i]);
            else
                //否则则用ming尝试更新
                ans=max(ans,ming[x][i]);
            x=f[x][i];
        }
    return ans;
}
int main(){
    n=read(),m=read();
    for(LL i=1;i<=m;i++) e[i].scan();
    kruskal();
    dep[1]=1;
    maxg[1][0]=0;
    ming[1][0]=-INF;
    dfs(1,0);
    LL _MST_=INF;
    for(LL i=1;i<=m;i++){
        LL u=e[i].u;
        LL v=e[i].v;
        LL w=e[i].w;
        if(!e[i].bt){
            LL lca=LCA(u,v);
            LL maxx=qmax(u,lca,w);
            LL maxy=qmax(v,lca,w);
            _MST_=min(_MST_,MST-max(maxx,maxy)+w);
        }
    }
    return printf("%lld",_MST_),0;
}

调了一天才调出来的正解，希望有帮助吧$qwq$

题解 P4180 【模板】严格次小生成树[BJWC2010]

原文：https://www.cnblogs.com/zsbzsb/p/11000505.html