洛谷 P4180 [BJWC2010] 次小生成树 题解【LCT】【生成树】

点击量：299

这个题LCT做还是麻烦了一点……

目录

题目描述

小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小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 蒙了，他找到了你，希望你帮他解决这个问题。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

5 6
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6 

输出样例#1：

11

说明

数据中无向图无自环；

$ 50\%$的数据$ N\le 2000,M\le 3000$；

$ 80\%$的数据$ N\le 50000,M\le 100 000$；

$ 100\%$的数据$ N\le 100000,M\le 300000$，边权值非负且不超过$ 10^9$。

题解：

第一眼看上去是一个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<b_1+b_2\qquad(1)
$$
但是这个不等式可以有多种情况，我们现在已经把$ {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;
}