洛谷P4180 [Beijing2010组队]次小生成树Tree（最小生成树,LCT,主席树,倍增LCA,倍增,树链剖分）

2022-11-18 16:24:34

洛谷题目传送门

%%%TPLY巨佬和ysner巨佬%%% 他们的题解

思路分析

具体思路都在各位巨佬的题解中。这题做法挺多的，我就不对每个都详细讲了，泛泛而谈吧。

大多数算法都要用kruskal把最小生成树弄出来，因为要求次小生成树。至于为什么次小一定只在最小的基础上改变了一条边，我也不会严谨的证明。。。。。。打表找规律大法好

剩下的可以有一堆数据结构来维护最大值和次大值（原理两位巨佬都讲清楚了，这里只分析一下算法的优劣）

  1. kruscal+倍增+LCA

    山楠巨佬的做法，我也写了这一种。复杂度\(O(MlogM(kruscal)+MlogN(\)倍增\(+LCA))\)常数较小，思路简单，详见山楠巨佬的题解。缺点是容易写挂，尤其是倍增部分。。。。。。（我写了半个上午+大半个下午）

    还要注意维护最大值和次大值的倍增状态转移，具体详见最下方的代码。
  2. kruscal+树剖

    思路也很简单（跟上面差不多），可以背模板（但不好打），然而我并不会。只不过复杂度也为\(O(MlogM+MlogN)\)，常数也不够小。

    update:会树剖了，维护链信息应该是\(O(Mlog^2N)\)的，不是很优秀啊。。。。。。
  3. LCT

    思路还是很简单，拆点维护边权（LCT总结此部分更新完啦），用LCT维护最小生成树，能link就link，不能就挑出两个点split一下来查询最大/次大值更新答案。复杂度正确\(O(MlogM)\)，但常数巨大（天平巨佬和XZY巨佬都被卡常了。。。。。。），搞得我不敢做。。。。。。（update：突然心血来潮，用LCT把这道题也做啦！代码放在最下面）
  4. kruscal+主席树+LCA

    自己yy出来的，只是未实现。毕竟用到这一题上面还是有点大材小用了。

    参考一下count on a tree这道题和我的题解。

    同样对于最小生成树边权按降序离散化后，建立主席树（并不用拆点，以点权作为点的父边的边权），查询跳\(u,v,lca(u,v)\)三个点，算\(size[lc[u]]+size[lc[v]]-2×size[lc[lca]]\)。我们不查排名了，直接找排名最小的值，能往左跳（上式结果大于0）就往左，假如最大值等于当前枚举到的边权（不能构成严格次小生成树），就return回去找次大值。复杂度正确，\(O(MlogM+MlogN)\)，常数应该也不错（没有二维数组，而且不用刻意维护次大值），但比方法1估计还是要低效一点（查询是满的log，方法1基本不满）
  5. （蒟蒻闲扯中，求Dalao勿喷）

    我很希望，用一种贪心的思想来去掉前面除kruskal部分以外的log复杂度。因为边集已经排好序，我们算答案的时候，后面的权值一定大于等于前面，算贡献的时候可以贪心。于是想暴力查询并维护已查询的边，下次查的时候就利用之前的信息就好了。

    这样对于非严格次小生成树是可做的，非常贪心，找完的最小生成树边，算完贡献就删掉了。因为后面枚举到的非最小生成树边，在找的最小生成树边中，假如当前找到一个以前找过的最小生成树边，那么当前产生的贡献一定小于等于以前产生的贡献。所以删掉就没问题啦！

    但是，这里要求是严格次小，那我们在找的时候，可能有某个最小生成树边严格等于当前枚举到的非树边，那么当前不能算贡献，但以后可以啊！

    那么可不可以暂时先不删掉这些当前严格等于的边呢？这样是对的，但是假如构造出一组数据，使得绝大部分边权值完全一样，那么每一次枚举非树边都不能删掉，复杂度退化到\(O(N(M-N))\)，不敢这样做（但愿数据较水，不卡这种方法）

    还有可能可以维护以前查询过的最大值。但我还是太弱了，并没有想到很好的能仅仅以线性时间复杂度的代价就能维护此信息的方法，Dalao们有想法欢迎指教。

kruscal+倍增+LCA

又看到不少巨佬被卡常了，于是我打算拿这题来练练卡常技巧。效果很不错，yyb_test没开氧气就704ms到rank1了。还是分享一下吧。

register，inline，fread是不能少的。另外，ST表是个二位数组，调用需要较大常数。我们发此题倍增需要维护3个量（每个点的\(2^j\)的祖先（用于LCA)，到这个祖先路径上的边权最大值、次大值），而且不管是预处理还是查询的时候，三个量都是捆绑在一起的。于是我干脆把他们放在一个struct里面了。然后开一个临时register指针指向当前的维度，防止反复调用二位数组。大概就是这样，我也没法很清楚地描述，看看代码吧。

#include<cstdio>

#include<algorithm>

using namespace std;

#define R register

#define max(x,y) x>y?x:y//返回最大值

#define maxp(x,y) if(x<y)x=y;//更新最大值

#define in(z)\

    while(*++p<'-');\

    z=*p&15;\

    while(*++p>'-')z*=10,z+=*p&15//读优

const int N=100009,M=300009;

long long sum;//注意不能开int

char s[M<<5];

bool mst[M];

int P,he[N],ne[N<<1],to[N<<1],len[N<<1],ff[N],b[N],d[N];

struct ST{

    int f,m1,m2;

}st[N][18];//封起来

struct EDGE{

    int u,v,l;

    inline bool operator<(EDGE x)const{//用于sort

        return l<x.l;

    }

    inline void add(){//将该边加入最小生成树

        sum+=l;

        to[++P]=v;ne[P]=he[u];he[u]=P;len[P]=l;

        to[++P]=u;ne[P]=he[v];he[v]=P;len[P]=l;

    }

}e[M];

void dfs(R int u,R int fa){//建树，预处理

    d[u]=d[fa]+1;

    st[u][0].f=fa;

    R ST*a,*l,*r;//卡常指针,a总区间,l上区间,r下区间

    //可忽略下面一行（极其丑陋）

    for(R int&i=b[u];((a=&st[u][i+1])->f=(l=&st[(r=&st[u][i])->f][i])->f);++i){

             if(l->m1>r->m1)a->m1=l->m1,a->m2=max(l->m2,r->m1);

        else if(r->m1>l->m1)a->m1=r->m1,a->m2=max(r->m2,l->m1);

        else                a->m1=l->m1,a->m2=max(l->m2,r->m2);//注意认真分析最大和次大的转移

    }

    for(R int i=he[u];i;i=ne[i])

        if(to[i]!=fa)st[to[i]][0].m1=len[i],dfs(to[i],u);

}

int getf(R int x){//并查集

    if(x!=ff[x])return ff[x]=getf(ff[x]);

    return x;

}

int main(){

    fread(s,1,sizeof(s),stdin);//卡常

    R char*p=s-1;//再卡常

    R ST*l,*r;//还是卡常

    R int n,m,i,j,k,x,y,now,nl,ans=2147483647;

    in(n);in(m);

    for(i=1;i<=m;++i){

        in(e[i].u);in(e[i].v);in(e[i].l);

    }

    //kruscal开始

    sort(e+1,e+m+1);

    for(i=1;i<=n;++i)ff[i]=i;

    for(i=1;P>>1<n-1;++i){

        x=getf(ff[e[i].u]);y=getf(ff[e[i].v]);

        if(x==y)continue;

        mst[i]=1;//标记为树边

        ff[x]=y;

        e[i].add();

    }

    dfs(1,0);

    for(i=1;i<=m;++i){

        if(mst[i])continue;

        x=e[i].u;y=e[i].v;now=0;nl=e[i].l;

        //倍增，跳LCA以及更新当前最大贡献

        if(d[x]<d[y])j=x,x=y,y=j;

        for(j=0,k=d[x]-d[y];k;++j,k>>=1){//调整至深度相同

            if(k&1){

                if((l=&st[x][j])->m1!=nl){maxp(now,l->m1);}

                else{maxp(now,l->m2);}

                x=l->f;

                }

            }

        if(x==y)goto F;//不用跳LCA了，下面直接跳过

        for(j=b[x];j>=0;--j){

            if((l=&st[x][j])->f==(r=&st[y][j])->f)continue;

            if(l->m1!=nl){maxp(now,l->m1);}

            else{maxp(now,l->m2);}//判断用最大还是次大更新

            if(r->m1!=nl){maxp(now,r->m1);}

            else{maxp(now,r->m2);}

            x=l->f;y=r->f;

        }

//注意下面几行，还没跳到LCA上，还要算父边有没有贡献（害我WA了N回）

        if((l=&st[x][0])->m1!=nl){maxp(now,l->m1);}

        else{maxp(now,l->m2);}

        if((r=&st[y][0])->m1!=nl){maxp(now,r->m1);}

        else{maxp(now,r->m2);}

      F:if(ans>nl-now)ans=nl-now;

    }

    printf("%lld\n",sum+ans);

    return 0;

}

LCT

其实可能TPLY巨佬有一个小问题导致常数过大。因为LCT可以动态维护最小生成树，所以kruskal、建树、枚举尝试更新答案这几步分开做有些多余了。其实这些步骤可以合在一起，等于说整个边集只要排好序后，只要从小到大扫一遍就好啦。扫的过程中，如果两个点没连通就连起来，如果联通了，就直接split两个点并更新答案。

当然了，连通性的维护能用并查集肯定尽量用，findroot太慢会T。

试一下主动拒绝氧气的滋养？！然后我就过了，最后两个点960+ms？！（不好意思TPLY巨佬）

后来发现忘了fread，于是又交一波，最后一个点T？！

难道写的define反复调用结构体导致太慢？为了卡常又魔改了一下，最终最后一个点800ms左右过。

贴一下极简主义丑陋的LCT代码

#include<cstdio>

#include<algorithm>

using namespace std;

#define R register int

#define I inline void

#define lc c[x][0]

#define rc c[x][1]

#define in(z) ini=&z;\//用指针优化一下

    while(*++q<'-');\

    *ini=*q&15;\

    while(*++q>'-')*ini*=10,*ini+=*q&15

const int N=100009,M=200009;

int f[M],c[M][2],v[M],mx[M],mx2[M],ff[N];//ff并查集

bool r[M];

char str[M<<6];

struct EDGE{

    int u,v,l;

    inline bool operator<(EDGE x)const{

        return l<x.l;

    }

}e[300009];

inline bool nroot(R x){

    return c[f[x]][0]==x||c[f[x]][1]==x;

}

I pushup(R x){

    R l=lc,r=rc;

         if(mx[l]>mx[r])mx[x]=mx[l],mx2[x]=max(mx2[l],mx[r]);

    else if(mx[r]>mx[l])mx[x]=mx[r],mx2[x]=max(mx2[r],mx[l]);

    else                mx[x]=mx[l],mx2[x]=max(mx2[l],mx2[r]);

         if(v[x]>mx[x]) mx2[x]=mx[x],mx[x]=v[x];

    else if(v[x]!=mx[x]&&v[x]>mx2[x])mx2[x]=v[x];

}//想维护个次大值怎么就那么麻烦啊。。。。。。（与倍增不同，除了左右儿子，自己也要考虑）

I pushdown(R x){

    if(r[x]){

        R t=lc;

        r[lc=rc]^=1;r[rc=t]^=1;r[x]=0;

    }

}

I pushall(R x){

    if(nroot(x))pushall(f[x]);

    pushdown(x);

}//又用函数堆栈pushdown

I rotate(R x){

    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];

    if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;

    f[w]=y;f[y]=x;f[x]=z;

    pushup(y);

}

I splay(R x){

    R y=x;

    pushall(x);

    while(nroot(x)){

        if(nroot(y=f[x]))

            rotate((c[y][0]==x)^(c[f[y]][0]==y)?x:y);

        rotate(x);

    }

    pushup(x);

}

I access(R x){

    for(R y=0;x;x=f[y=x])

        splay(x),rc=y,pushup(x);

}

I mroot(R x){

    access(x);splay(x);

    r[x]^=1;

}//以上LCT，split和link写main函数里面去啦

int getf(R x){

    if(x==ff[x])return x;

    return ff[x]=getf(ff[x]);

}//并查集代替了findroot

int main(){

    fread(str,1,sizeof(str),stdin);

    R n,m,p,i,x,y,ans=2147483647,*ini;

    register char*q=str-1;

    register long long sum=0;

    in(n);in(m);p=n;//p用来区分点和边（在LCT里都是点）

    for(i=1;i<=n;++i)

        ff[i]=i;//初始化

    for(i=1;i<=m;++i){

        in(e[i].u);in(e[i].v);in(e[i].l);

    }

    sort(e+1,e+m+1);

    for(i=1;i<=m;++i){

        if(getf(x=e[i].u)==getf(y=e[i].v)){

            mroot(x);

            access(y);splay(y);

            ans=min(ans,e[i].l-(e[i].l>mx[y]?mx[y]:mx2[y]));

        }//如果连完了直接更新答案

        else{

            mroot(x);

    		f[f[x]=++p]=y;//点连边，边连点，顺序一定要保证

    		sum+=mx[p]=v[p]=e[i].l;//边权放进LCT里面

    		ff[ff[x]]=ff[y];//并查集合并

        }

    }

    printf("%lld\n",sum+ans);

    return 0;

}
上一篇：『重构--改善既有代码的设计』读书笔记----Replace Method with Method Object


下一篇：Enhancing the Scalability of Memcached