[BZOJ1977][BeiJing2010组队]次小生成树 Tree 最小生成树+倍增LCA


原题链接
给定一个图,求此图的严格次小生成树.
容易证明严格次小生成树有且仅有一条边是不可能出现在最小生成树上的,因此我们可以求出最小生成树后枚举这条非树边.
考虑到添加一条非树边时,树上将形成一个环,那么只需要找出环上最长的一条边,用非树边代替它,就得到了一棵新生成树.实现方法是使用倍增LCA求链上最小值,并维护最小增量即可.
然而,这样求出的是非严格次小生成树,因为可能和最小生成树相等.因此还要维护链上次小值保证严格性.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 102333
#define M 302333
using namespace std;
typedef long long ll;
const ll inf=0x3bbbbbbbbbbbbbbbll;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
    return x;
}
int n,m;
struct Node
{
    int x,y;
    ll z;
    inline void red()
    {
        x=read();y=read();z=read();
    }
}e[M];
bool v[M];
inline bool operator<(const Node &a,const Node &b)
{
    return a.z<b.z;
}
int head[N],to[N<<1],nxt[N<<1],tot;
ll val[N<<1];
inline void add(int x,int y,int z)
{
    to[++tot]=y;
    val[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
ll ans;
int ufs[N];
void ufs_init()
{
    for(int i=1;i<=n;++i)ufs[i]=i;
}
int find(int x)
{
    return x==ufs[x]?x:(ufs[x]=find(ufs[x]));
}
inline int merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return 0;
    ufs[x]=y;return 1;
}
ll Max[N][20],sec[N][20];
int fa[N][20],deep[N],Log[N];
void build_tree()
{
    ufs_init();
    sort(e+1,e+m+1);
    for(int i=1;i<=m;++i)
    {
        v[i]=merge(e[i].x,e[i].y);
        if(v[i])ans+=e[i].z,add(e[i].x,e[i].y,e[i].z),add(e[i].y,e[i].x,e[i].z);
    }
    memset(Max,0xc0,sizeof Max),memset(sec,0xc0,sizeof sec);
}
void dfs(int x)
{
    deep[x]=deep[fa[x][0]]+1;
    for(int i=head[x];i;i=nxt[i])if(to[i]!=fa[x][0])
    {
        fa[to[i]][0]=x;
        Max[to[i]][0]=val[i];
        dfs(to[i]);
    }
}
inline ll getsecond(ll a,ll b,ll c,ll d)
{
    ll T[4];
    T[0]=a,T[1]=b,T[2]=c,T[3]=d;
    sort(T,T+4);
    for(int i=1;i<4;++i)if(T[i]>T[i-1])return T[i];
    return inf;
}
void lca_init()
{
    dfs(1);
    for(int i=2;i<=n;++i)Log[i]=Log[i>>1]+1;
    for(int j,i=1;i<=Log[n];++i)
        for(j=1;j<=n;++j)
        {
            fa[j][i]=fa[fa[j][i-1]][i-1];
            Max[j][i]=max(Max[j][i-1],Max[fa[j][i-1]][i-1]);
            sec[j][i]=getsecond(Max[j][i-1],Max[fa[j][i-1]][i-1],sec[j][i-1],sec[fa[j][i-1]][i-1]);
        }
}
struct par{ll x,y;};
inline par getsec(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int i;
    ll re1=-inf,re2=-inf;
    for(i=Log[deep[x]];i+1;--i)if(deep[fa[x][i]]>=deep[y])
    {
        re1=max(re1,Max[x][i]);
        if(Max[x][i]<re1)re2=max(re2,Max[x][i]);
        re2=max(re2,sec[x][i]);
        x=fa[x][i];
    }
    if(x==y)return (par){re1,re2};
    for(i=Log[deep[x]];i+1;--i)if(fa[x][i]!=fa[y][i])
    {
        re1=max(re1,Max[x][i]);
        if(Max[x][i]<re1)re2=max(re2,Max[x][i]);
        re2=max(re2,sec[x][i]);
        re1=max(re1,Max[y][i]);
        if(Max[y][i]<re1)re2=max(re2,Max[y][i]);
        re2=max(re2,sec[y][i]);
        x=fa[x][i],y=fa[y][i];
    }
    re1=max(re1,Max[x][0]);
    if(Max[x][0]<re1)re2=max(re2,Max[x][0]);
    re1=max(re1,Max[y][0]);
    if(Max[y][0]<re1)re2=max(re2,Max[y][0]);
    return (par){re1,re2};
}
ll mindelta=inf;
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)e[i].red();
    build_tree();
    lca_init();
    int x,y,i;
    ll z;par t;
    for(i=1;i<=m;++i)if(!v[i])
    {
        x=e[i].x,y=e[i].y,z=e[i].z;
        t=getsec(x,y);
        if(z!=t.x)mindelta=min(mindelta,z-t.x);
        mindelta=min(mindelta,z-t.y);
    }
    cout<<ans+mindelta;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注