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

· · 题解

个人认为这篇题解有助于理解

一、总体思路

首先,我这一题的思路是倍增LCA+Kruskal

没学过这两个算法没关系，后面有讲解

时间复杂度O(nlog_2n+mlog_2m)

(倍增O(nlog_nn)+Kruskal O(mlog_2m+m\alpha(n)))

--- ## 二、补习算法（会的请跳过） ### 1.倍增LCA 形象地说，倍增算法是一种**“高级小抄”** 假设我是一个小朋友考试要考1+n=? 我不会，于是我开始打小抄： - 1+1=2 - 1+2=3 - 1+3=4 - …… 这是普通小抄 但是老师很坑，$n<=2^{10000}

考试时：

老师：dijstra0分,站起来解释一下

dijstra：我用了IO优化，可是小抄只打了...

这时呢，倍增大佬横空出世

倍增大佬：我用 cin/cout 打完了

于是dijstra很佩服，付给倍增大佬2^{10000},要求学习打小抄

倍增大佬：我把 2^{1-10000}抄了下来，然后就GG了

树上倍增： 用bz数组存一下，bz[i][j]表示i点上面的第2^j个祖先

1.预处理（伪代码）

    for j 1 .. 18
        for i 1 .. n
            bz[i][j] = bz[bz[i][j-1]][j-1]

2.求LCA

    LCA(u,v)
    {
        if < u的深度 小于 v的深度 >
        {
            swap(u , v);
        }

        for i 18 .. 0
            if < u 向上跳还是 比 v 低 >
            {
                u 向上跳
            }

        if < u , v 重合> 
        {
            return u 
        }

        for i 18 .. 0
        {
            if < u 向上跳 , v 向上跳 未重合 >
            {
                u 向上跳
                v 向上跳
            }
        }

        return u
    }

推荐题目

2.kruskal

不用**并查集**就会很慢 ##### 并查集($O(\alpha(n))$) *路径压缩：代码只有一行，却是灵魂所在。它是在查询时'顺便'存一下* *伪代码：* ```cpp Father[N] for i 1 .. N Father[i] = i //初始化 Get_Father( x ) { if x=Father[x] return x else return Father[x]=Get_Father(Father[x]) } //路径压缩 Merge( u , v ) { Father_u = Get_Father(u) Father_v = Get_Father(v) if Father_u != Father v //不在一个联通块内 { Father [ Father_u ] = Father_v } } ``` ##### $kruskal

将边按照边权排序

从小到大扫

不在联通块内就连边

伪代码

sort;
for i 1 .. m
{
    if <不在同一联通快>
    {
        Merge
        Ans+=边权
    }
}

推荐题目

带权并查集

最小生成树

四、解决方案

  1. 首先，kruskal 求最小生成树
  2. 求次小生成树

关键在于次小生成树怎么求：

问自己一些问题

  1. 怎么求不严格次小生成树

  2. 不严格次小生成树为什么不严格

仔细思考上面两个问题，然后带着问题阅读以下部分

dijstra：回归本质

扪心自问，kruskal 的本质是什么？

贪心

有u到v之间边权最大值小于等于u到v未选入的边的边权 所以说，**不严格**次小生成树只要 **遍历每条未选的边(u,v,d)，用它替换u和v之间的最大边即可** --- 现在我们的任务就是把**不严格**的**不**去掉 **为什么**它不**严格**？ 因为 u到v之间边权最大值小于**等于**u到v未选入的边的边权 等于！ 是不是感觉自己被坑了？ --- 没关系，我们只要多存一个**次大值**即可 指出一句，attack的题解对次大值合并时有一处疏忽，他的代码会在合并两个相等的最大值时**最大=次大** 一切最大次大都在**倍增**时处理 ## 五、注意事项 1. 开long long(int64) 2. INF 开大(我开2147483647炸了) ## 六、贴代码 (我知道你们只看**这个**) ```cpp #include<bits/stdc++.h> #define N 400010 #define M 900010 #define INF 2147483647000000 #define ll long long using namespace std; struct edge{ ll u,v,d; ll next; }G[N<<1]; ll tot=0; ll head[N]; inline void addedge(ll u,ll v,ll d) { G[++tot].u=u,G[tot].v=v,G[tot].d=d,G[tot].next=head[u],head[u]=tot; G[++tot].u=v,G[tot].v=u,G[tot].d=d,G[tot].next=head[v],head[v]=tot; } ll bz[N][19]; ll maxi[N][19]; ll mini[N][19]; ll deep[N]; inline void dfs(ll u,ll fa) { bz[u][0]=fa; for(ll i=head[u];i;i=G[i].next) { ll v=G[i].v; if(v==fa)continue; deep[v]=deep[u]+1ll; maxi[v][0]=G[i].d; mini[v][0]=-INF; dfs(v,u); } } ll n; inline void cal() { for(ll i=1;i<=18;++i) for(ll j=1;j<=n;++j) { bz[j][i]=bz[bz[j][i-1]][i-1]; maxi[j][i]=max(maxi[j][i-1],maxi[bz[j][i-1]][i-1]); mini[j][i]=max(mini[j][i-1],mini[bz[j][i-1]][i-1]); if(maxi[j][i-1]>maxi[bz[j][i-1]][i-1])mini[j][i]=max(mini[j][i],maxi[bz[j][i-1]][i-1]); else if(maxi[j][i-1]<maxi[bz[j][i-1]][i-1])mini[j][i]=max(mini[j][i],maxi[j][i-1]); } } inline ll LCA(ll x,ll y) { if(deep[x]<deep[y])swap(x,y); for(ll i=18;i>=0;--i) if(deep[bz[x][i]]>=deep[y]) x=bz[x][i]; if(x==y)return x; for(ll i=18;i>=0;--i) if(bz[x][i]^bz[y][i]) x=bz[x][i],y=bz[y][i]; return bz[x][0]; } inline ll qmax(ll u,ll v,ll maxx) { ll Ans=-INF; for(ll i=18;i>=0;--i) { if(deep[bz[u][i]]>=deep[v]) { if(maxx!=maxi[u][i])Ans=max(Ans,maxi[u][i]); else Ans=max(Ans,mini[u][i]); u=bz[u][i]; } } return Ans; } inline void read(ll &x) { x=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar(); } ll m; edge A[M<<1]; inline bool cmp(edge x,edge y) { return x.d<y.d; } ll Father[N]; inline ll Get_Father(ll x) { return (x==Father[x]) ? x : Father[x]=Get_Father(Father[x]); } bool B[M<<1]; int main() { read(n),read(m); for(ll i=1;i<=m;++i) { read(A[i].u),read(A[i].v),read(A[i].d); } sort(A+1,A+m+1,cmp); for(ll i=1;i<=n;++i) Father[i]=i; ll Cnt=0ll; for(ll i=1;i<=m;++i) { ll Father_u=Get_Father(A[i].u); ll Father_v=Get_Father(A[i].v); if(Father_u!=Father_v) { Cnt+=A[i].d; Father[Father_u]=Father_v; addedge(A[i].u,A[i].v,A[i].d); B[i]=true; } } mini[1][0]=-INF; deep[1]=1; dfs(1,-1); cal(); ll Ans=INF; for(ll i=1;i<=m;++i) { if(!B[i]) { ll u=A[i].u; ll v=A[i].v; ll d=A[i].d; ll lca=LCA(u,v); ll maxu=qmax(u,lca,d); ll maxv=qmax(v,lca,d); Ans=min(Ans,Cnt-max(maxu,maxv)+d); } } printf("%lld",Ans); return 0; } ```