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

wjyyy · 2019-01-07 20:12:14 · 题解

给大常数lct选手一个救赎的机会。

博客地址：传送门

题解：

第一眼看上去是一个lct维护生成树的问题。然而没有动态加删边，可能是大材小用。

不过用lct直接维护生成树也有一定的问题。如果我们枚举不在生成树上的边，找环并删除环上边权小于当前边的权值最大的边，也许并不能保证最小生成树与(严格)次小生成树只相差一对边。

实际上是可以的。我们用反证法稍微考虑一下最小生成树(MST)与(严格)次小生成树(SST)相差两对边的情况。

_如果MST和SST相差两对边，假设分别为\{a_1,b_1\},\{a_2,b_2\}，也就是说\{a_1,a_2\}在MST上，\{b_1,b_2\}在SST上。那么一定有_

_但是这个不等式可以有多种情况，我们现在已经把\{a_1,a_2\}删掉了，还要加回两条边（不为原来的边）使得图重新构成一棵生成树，可以有\{a_1,b_1\},\{a_1,b_2\},\{a_2,b_2\},\{a_2,b_1\},\{b_1,b_2\}这五种情况。但是无论如何，\{b_1,b_2\}都不会是这五组中最小的。_

_假设a_1\le a_2,b_1\le b_2，若a_1<b_1，则\{a_1,b_2\}一定在次小生成树上了了，若a_1\ge b_1，由不等式(1)，一定有a_2<b_2，那么此时\{a_2,b_1\}就最优了。_

证毕。

那么此时就考虑查询一条链上小于x的最大边权来更新答案。因为lct是用splay做的，所以可以维护链上的最大值和次大值，大致是这样的：

void maintain(int k)
{
    sum[k]=Max(Max(sum[ls],key[k]),sum[rs]);//维护最大值
    ssum[k]=0;//次大值
    ssum[k]=(sum[ls]<sum[k]&&sum[ls]>ssum[k])?sum[ls]:ssum[k];//次大值只可能在这四种中出现
    ssum[k]=(key[k]<sum[k]&&key[k]>ssum[k])?key[k]:ssum[k];
    ssum[k]=(ssum[ls]<sum[k]&&ssum[ls]>ssum[k])?ssum[ls]:ssum[k];
    ssum[k]=(ssum[rs]<sum[k]&&ssum[rs]>ssum[k])?ssum[rs]:ssum[k];
}

常数是原来的3倍多。轻而易举TLE。因此如果不是要练LCT还是建议大家写倍增/树剖。

不过我们可以提取出来这条链然后dfs这棵子splay，带入参数x，找到小于x的最大边权。既然我们已经维护了子树最大值，就可以剪枝，对，就是剪枝。如果子树最大值小于x了，直接用最大值更新答案并返回，否则继续dfs。

这种操作的最坏复杂度是O(nm)的，一条构造过的链应该可以卡得掉。不过数据强度不是很大，剪枝效果比较好，O2最慢的点也只跑了709ms。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
int read()
{
    char ch=getchar();
    int x=0;
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
int Max(int x,int y)
{
    return x>y?x:y;
}
int ch[2][401000],fa[401000];
int key[401000],sum[401000],lazy[401000];
void pushdown(int k)
{
    if(lazy[k])
    {
        lazy[k]=0;
        int tmp=ls;
        ls=rs;
        rs=tmp;
        lazy[ls]^=1;
        lazy[rs]^=1;
    }
}
void maintain(int k)
{
    sum[k]=Max(Max(sum[ls],key[k]),sum[rs]);
}
void Rotate(int k)
{
    int y=fa[k];
    if(!isroot(y))
        ch[which(y)][fa[y]]=k;
    bool d=which(k);
    fa[k]=fa[y];
    fa[y]=k;
    ch[d][y]=ch[!d][k];
    fa[ch[d][y]]=y;
    ch[!d][k]=y;
    maintain(y);
    maintain(k);
}
int stk[401000],tp=0;
void splay(int k)
{
    while(!isroot(k))
    {
        stk[++tp]=k;
        k=fa[k];
    }
    stk[++tp]=k;
    int qaq=fa[k];
    while(tp)
        pushdown(stk[tp--]);
    k=stk[1];
    while(fa[k]!=qaq)
    {
        int y=fa[k];
        if(!isroot(y))
            Rotate(which(k)^which(y)?k:y);
        Rotate(k);
    }
}
void access(int k)
{
    for(register int x=k,y=0;x;y=x,x=fa[x])
    {
        splay(x);
        ch[1][x]=y;
        maintain(x);
    }
}
void makeroot(int k)
{
    access(k);
    splay(k);
    lazy[k]^=1;
}
int getroot(int k)
{
    access(k);
    splay(k);
    while(ls)
        k=ls;
    return k;
}
void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
int Find(int k,int x)//在splay中找小于x的最大值
{
    int tmp=0;
    if(key[k]<x)//先比较当前节点
        tmp=key[k];
    if(sum[ls]<x)//决策进不进入左儿子
        tmp=tmp>sum[ls]?tmp:sum[ls];
    else
    {
        int y=Find(ls,x);
        tmp=tmp>y?tmp:y;
    }
    if(sum[rs]<x)//右儿子
        tmp=tmp>sum[rs]?tmp:sum[rs];
    else
    {
        int y=Find(rs,x);
        tmp=tmp>y?tmp:y;
    }
    return tmp;
}
struct edge
{
    int x,y,w;
    friend bool operator <(edge a,edge b)
    {
        return a.w<b.w;
    }
}e[300100];
bool used[300100];
int main()
{
    int n,m;
    long long Sum=0,ans=1e18;
    n=read();
    m=read();
    for(int i=1;i<=m;++i)
    {
        e[i].x=read();
        e[i].y=read();
        e[i].w=read();
    }
    std::sort(e+1,e+1+m);
    for(int i=1;i<=m;++i)
    {
        key[n+i]=sum[n+i]=e[i].w;
        makeroot(e[i].x);
        if(getroot(e[i].y)!=e[i].x)
        {
            used[i]=1;
            link(e[i].x,n+i);
            link(e[i].y,n+i);
            Sum+=e[i].w;
        }
    }
    for(int i=1;i<=m;++i)
        if(!used[i])
        {
            split(e[i].x,e[i].y);
            int t=Find(e[i].y,e[i].w);//不超过e[i].w
            ans=ans<Sum+key[n+i]-t?ans:Sum+key[n+i]-t;
        }
    printf("%lld\n",ans);
    return 0;
}