题解 P4180【【模板】严格次小生成树[BJWC2010] 一本通提高篇 3.1.6 1493 次小生成树】

lzcjoe · 2019-08-12 15:40:24 · 题解

题面

1493：次小生成树

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

原题来自：BeiJing 2010 组队赛

给定一张 N 个点 M 条边的无向图，求无向图的严格次小生成树。

设最小生成树的边权之和为 sum，严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。

【输入】

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

【输出】

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

【输入样例】

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

【输出样例】

【提示】

数据范围：

对于全部数据，1≤N≤10^5,1≤M≤3×10^5，数据中无向图无自环，边权值非负且不超过 10^9。

算法

次小生成树算法

非严格次小生成树算法

先使用最小生成树算法（Kruscal）计算最小生成树边权和，再逐一枚举新加的一条边（次小生成树一点是在最小生成树中删去一条边、增加一条边），此时会出现一个环，将环上除了添加的边以外的最大的边删去（贪心），即可得到一种生成树的方法，更新新的生成树的边权和的最小值即可。

但题目要求严格次小生成树（边权和严格大于最小生成树的边权和）时这种贪心的方法是不正确的，反例如下：

此图的次小生成树边权和为11（1-2，2-4，3-4，3-5）。

可以在最小生成树中加上3-4边删去1-3边，但此算法在加入3-4边时处理1-2-4-3-1的环时最大值在2-4边，为3，此时次小生成树的边权与最小生成树一样，因为要求严格次小生成树，不会考虑，而会选择用加上4-5边，结果为12，不符。

严格次小生成树生成树算法（Kruskal+树上倍增lca）

Kruskal

求解最小生成树，再根据最小生成树的边权和更换边计算严格最小生成树。

树上倍增lca

求解最小生成树后，通过替换最小生成树上的边可以求解次小生成树。

在非严格次小生成树中，新添加的边的边权一定不小于最大值（否则就不是最小生成树），不能求出严格次小生成树（最大边可能等于添加的边的权值）。因此，对于严格次小生成树来说，不仅要求环上的最大值，还要求环上的次大值，这样在出现最大值等于边权时可以用次大值更新答案，保证答案正确性。

设g[x][i] , maxl[x][i] , secl[x][i] 分别表示在树上从x点向上走2^i层的结点编号、x点向上走2^i层遇到的边权的最大值、x点向上走2^i层遇到的边权的次大值，设i点与j点的最近公共祖先为k，则可以通过二进制分解和迭代得到i-k的最大值、次大值和j-k的最大值、次大值，枚举每一条不在最小生成树上的边更新答案即可。

代码

80 TLE：

#include<cstdio>
#include<algorithm>
#define maxi(a,b) ((a)>(b)?(a):(b))

unsigned int n,m;

struct pic
{
    unsigned int u,v,w;
    char book;
    bool operator < (const pic &a) const
    {
        return w<a.w;
    }
}edge[300005];//存图

unsigned int father[100005];
unsigned int get_father(unsigned int a)
{
    if(father[a]==a)
    {
        return father[a];
    }
    father[a]=get_father(father[a]);
    return father[a];
}//并查集

unsigned int points;
unsigned long long int sum;
struct tree
{
    unsigned int to,next,w;
}tree[200005];
unsigned int cnt,head[100005];
void add(unsigned int u,unsigned int v,unsigned int w)
{
    cnt++;
    tree[cnt].to=v;
    tree[cnt].next=head[u];
    head[u]=cnt;
    tree[cnt].w=w;
}//链式前向心存树、建边

unsigned int deep[100005],maxl[100005][20],secl[100005][20],g[100005][20];
//倍增数组，deep为在树上的深度，其余的含义在前文已经描述

void dfs(unsigned int now)
{
    for(unsigned int i=head[now];i!=0;i=tree[i].next)
    {
        if(tree[i].to!=g[now][0])
        {
            deep[tree[i].to]=deep[now]+1;
            maxl[tree[i].to][0]=tree[i].w;
            g[tree[i].to][0]=now;
            dfs(tree[i].to);
        }
    }
}//DFS求点的深度和最大值、祖先初始化

unsigned long long int ans=999999999999999ull;
unsigned int get_lca(unsigned int u,unsigned int v)
{
    //假设u比j深
    if(deep[u]<deep[v])
    {
        //不成立，进行交换
        unsigned int t;
        t=u;
        u=v;
        v=t;
    }
    unsigned int i;
    for(i=0;i<=18;i++)
    {
        if((1<<i)>deep[u])
        {
            break;
        }
    }
    i--;
    //求u的深度对应最大二进制次数
    for(int j=i;j>=0;j--)
    {
        //从i开始枚举u、v之间的高度差
        if(deep[u]>=deep[v]+(1<<j))
        {
            u=g[u][j];
            //不断迭代u的值使其接近于v
        }
    }
    if(u==v)
    {
        //u、v在一个点，返回这个点的值
        return u;
    }
    //此时u、v在同一层
    for(int j=18;j>=0;j--)
    {
        //枚举祖先可能的层数，从大到小枚举，使分解唯一
        if(g[u][j]!=g[v][j])//祖先不同
        {
            u=g[u][j];
            v=g[v][j];
            //迭代更新u、v
        }
    }
    //此时找出的是距离公共祖先最近的两个点，距离为1层
    return g[u][0];
    //返回祖先值，即为最近公共祖先
}//树上倍增求lca

unsigned int get_ans(unsigned int u,unsigned int v,unsigned int w)
{
    //获取新增u->v构成的环中的最大值（次大值）
    unsigned int lca=get_lca(u,v),i,maxleft=0,maxright=0;
    for(i=0;i<=18;i++)
    {
        if((1<<i)>deep[u])
        {
            break;
        }
    }
    i--;
    //获取深度二进制
    for(int j=i;j>=0;j--)
    {
        //枚举u与公共祖先的链上的最大值（次大值）
        if(deep[u]>=deep[lca]+(1<<j))
        {
            if(maxl[u][j]!=w)
            {
                //最大值与边权相等
                maxleft=maxi(maxleft,maxl[u][j]);
                //取次大值
            }
            else
            {
                //取最大值
                maxleft=maxi(maxleft,secl[u][j]);
            }
            u=g[u][j];//迭代接近lca
        }
    }
    for(i=0;i<=18;i++)
    {
        if((1<<i)>deep[v])
        {
            break;
        }
    }
    i--;
    for(int j=i;j>=0;j--)
    {
        if(deep[v]>=deep[lca]+(1<<j))
        {
            if(maxl[v][j]!=w)
            {
                maxright=maxi(maxright,maxl[v][j]);
            }
            else
            {
                maxright=maxi(maxright,secl[v][j]);
            }
            v=g[v][j];
        }
    }
    //同理求v与公共祖先的链上的最大值（次大值）
    return maxi(maxleft,maxright);
}
int main()
{
    scanf("%u%u",&n,&m);
    for(unsigned int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for(unsigned int i=1;i<=m;i++)
    {
        scanf("%u%u%u",&edge[i].u,&edge[i].v,&edge[i].w);
        edge[i].book=0;
    }
    //初始化、读入
    std::sort(edge+1,edge+m+1);
    for(unsigned short int i=1;i<=m;i++)
    {
        unsigned int fu=get_father(edge[i].u),fv=get_father(edge[i].v);
        if(fu!=fv)
        {
            points++;
            sum+=edge[i].w;
            edge[i].book=1;
            father[fv]=fu;
            add(edge[i].u,edge[i].v,edge[i].w);
            add(edge[i].v,edge[i].u,edge[i].w);
            if(points==n-1)
            {
                break;
            }
        }
    }
    //Kruskal算法，并添加树上边
    dfs(1);
    //初始化深度、单层的最大值
    for(unsigned short int i=1;i<=18;i++)
    {
        for(unsigned short int j=1;j<=n;j++)
        //short int -> TLE
        {
            g[j][i]=g[g[j][i-1]][i-1];
            //向上2^i层的祖先就是向上2^i-1层的祖先向上2^i-1层的祖先
            maxl[j][i]=maxi(maxl[j][i-1],maxl[g[j][i-1]][i-1]);
            secl[j][i]=maxi(secl[j][i-1],secl[g[j][i-1]][i-1]);
            //最大值、次大值分别更新
            if(maxl[j][i-1]<maxl[g[j][i-1]][i-1] && secl[j][i]<maxl[j][i-1])
            {
                secl[j][i]=maxl[j][i-1];
            }
            else if(maxl[j][i-1]>maxl[g[j][i-1]][i-1] && secl[j][i]<maxl[g[j][i-1]][i-1])
            {
                secl[j][i]=maxl[g[j][i-1]][i-1];
            }
            //针对不同情况更新可能的次大值
        }
    }
    for(unsigned int i=1;i<=m;i++)
    {
        if(edge[i].book==0)
        {
            unsigned int j=get_ans(edge[i].u,edge[i].v,edge[i].w);
            if(j!=edge[i].w && ans>sum-j+edge[i].w)
            {
                ans=sum-j+edge[i].w;
            }
            //获取链上的最大值（次大值）并更新答案
        }
    }
    printf("%llu",ans);//输出答案
    return 0;
}

读入优化 + 各种卡常手段（++、--和,） + 改short

100 AC：

#include<cstdio>
#include<algorithm>
#define maxi(a,b) ((a)>(b)?(a):(b))
inline unsigned int fread()
{
    unsigned int x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}//读入优化
unsigned int n,m;
struct pic
{
    unsigned int u,v,w;
    char book;
    inline bool operator < (const pic &a) const
    {
        return w<a.w;
    }
}edge[300005];
unsigned int father[100005];
unsigned int get_father(unsigned int a)
{
    if(father[a]==a)
    {
        return father[a];
    }
    return father[a]=get_father(father[a]);
}
unsigned int points;
unsigned long long int sum;
struct tree
{
    unsigned int to,next,w;
}tree[200005];
unsigned int cnt,head[100005];
inline void add(unsigned int u,unsigned int v,unsigned int w)
{
    ++cnt,tree[cnt].to=v,tree[cnt].next=head[u],head[u]=cnt,tree[cnt].w=w;
}
unsigned int deep[100005],maxl[100005][20],secl[100005][20],g[100005][20];
void dfs(unsigned int now,unsigned int fa)
{
    unsigned int v;
    for(unsigned int i=head[now];i!=0;i=tree[i].next)
    {
        v=tree[i].to;
        if(v!=fa)
        {
            deep[v]=deep[now]+1,maxl[v][0]=tree[i].w,g[v][0]=now;
            dfs(v,now);
        }
    }
}
unsigned long long int ans=999999999999999ull;
unsigned int get_lca(unsigned int u,unsigned int v)
{
    if(deep[u]<deep[v])
    {
        unsigned int t;
        t=u,u=v,v=t;
    }
    for(register short int j=18;j>=0;--j)
    {
        if(deep[g[u][j]]>=deep[v])
        {
            u=g[u][j];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(register short int j=18;j>=0;--j)
    {
        if(g[u][j]!=g[v][j])
        {
            u=g[u][j],v=g[v][j];
        }
    }
    return g[u][0];
}
unsigned int get_ans(unsigned int u,unsigned int v,unsigned int w)
{
    unsigned int lca=get_lca(u,v),maxleft=0,maxright=0;
    for(register short int j=18;j>=0;--j)
    {
        if(deep[g[u][j]]>=deep[lca])
        {
            if(maxl[u][j]!=w)
            {
                maxleft=maxi(maxleft,maxl[u][j]);
            }
            else
            {
                maxleft=maxi(maxleft,secl[u][j]);
            }
            u=g[u][j];
        }
    }
    for(register short int j=18;j>=0;--j)
    {
        if(deep[g[v][j]]>=deep[lca])
        {
            if(maxl[v][j]!=w)
            {
                maxright=maxi(maxright,maxl[v][j]);
            }
            else
            {
                maxright=maxi(maxright,secl[v][j]);
            }
            v=g[v][j];
        }
    }
    return maxi(maxleft,maxright);
}
int main()
{
    n=fread(),m=fread();
    for(register unsigned int i=1;i<=n;++i)
    {
        father[i]=i;
    }
    for(register unsigned int i=1;i<=m;++i)
    {
        edge[i].u=fread(),edge[i].v=fread(),edge[i].w=fread();
    }
    std::sort(edge+1,edge+m+1);
    for(register unsigned int i=1;i<=m;++i)
    {
        register unsigned int fu=get_father(edge[i].u),fv=get_father(edge[i].v);
        if(fu!=fv)
        {
            ++points,sum+=edge[i].w,edge[i].book=1,father[fv]=fu;
            add(edge[i].u,edge[i].v,edge[i].w);
            add(edge[i].v,edge[i].u,edge[i].w);
            if(points==n-1)
            {
                break;
            }
        }
    }
    dfs(1,0);
    for(register unsigned short int i=1;i<=18;++i)
    {
        for(register unsigned int j=1;j<=n;++j)
        {
            g[j][i]=g[g[j][i-1]][i-1],maxl[j][i]=maxi(maxl[j][i-1],maxl[g[j][i-1]][i-1]),secl[j][i]=maxi(secl[j][i-1],secl[g[j][i-1]][i-1]);
            if(maxl[j][i-1]<maxl[g[j][i-1]][i-1] && secl[j][i]<maxl[j][i-1])
            {
                secl[j][i]=maxl[j][i-1];
            }
            else if(maxl[j][i-1]>maxl[g[j][i-1]][i-1] && secl[j][i]<maxl[g[j][i-1]][i-1])
            {
                secl[j][i]=maxl[g[j][i-1]][i-1];
            }
        }
    }
    for(register unsigned int i=1;i<=m;++i)
    {
        if(edge[i].book==0)
        {
            unsigned int j=get_ans(edge[i].u,edge[i].v,edge[i].w);
            if(j!=edge[i].w && ans>sum-j+edge[i].w)
            {
                ans=sum-j+edge[i].w;
            }
        }
    }
    printf("%llu",ans);
    return 0;
}

总算是AC了！

运行结果

一本通OJ：

1493

通过 100分

测试点1: 答案正确 312KB 1MS

测试点2: 答案正确 688KB 1MS

测试点3: 答案正确 680KB 1MS

测试点4: 答案正确 712KB 2MS

测试点5: 答案正确 1068KB 2MS

测试点6: 答案正确 21704KB 104MS

测试点7: 答案正确 19980KB 109MS

测试点8: 答案正确 19452KB 88MS

测试点9: 答案正确 41372KB 382MS

测试点10: 答案正确 40116KB 272MS

洛谷：

用时 1.44s 内存 32.70MB

测试点信息

6ms/8.62MB AC #1

4ms/1.04MB AC #2

6ms/10.63MB AC #3

6ms/10.88MB AC #4

5ms/1.26MB AC #5

201ms/27.55MB AC #6

150ms/15.88MB AC #7

102ms/15.25MB AC #8

658ms/32.70MB AC #9

302ms/31.57MB AC #10

//第2道AC的紫题