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

作者: wjyyy 分类: LCT,splay,数据结构,生成树,解题报告 发布时间: 2019-01-07 20:11

点击量:49

这个题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;
}

说点什么

avatar
  Subscribe  
提醒
更多阅读
/* */