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

· · 题解

其实这并不是一个模板题

一、题目

点此看题

二、解法

发现次小生成树和最小生成树只有一条边的差异，为什么呢？考虑每一条不在最小生成树上的边如果加上去的增量，发现它是非负的，要生成次小生成树，肯定要最小化增量，所以只替换一条边是最优的。

考虑每一条边去替换树上的边，先加入这条边，会与树形成一个环，发现环上的最大边就是我们替换的树边，但由于题目要求严格次小，就不能取和加入边权值相等的树边，暴力跑即可。

考虑对暴力优化，发现找最大边的过程本质就是一个Lca，我们用倍增维护最大值和次大值，然后跑Lca就行了，时间复杂度O(n\log n)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 100005;
const int inf = (1ll<<62);
int read()
{
    int x=0,flag=1;char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*flag;
}
int n,m,tot,ans=inf,f[MAXN],p[MAXN],dep[MAXN];
int fa[MAXN][20],Max[MAXN][20],sub[MAXN][20];
long long mst;
struct edge
{
    int v,c,next;
}e[2*MAXN];
struct node
{
    int u,v,c;
    bool operator < (const node &x) const
    {
        return c<x.c;
    }
}a[3*MAXN];
int op(int a,int b,int lim)
{
    if(a>=lim) return b>=lim?0:b;
    if(b>=lim) return a>=lim?0:a;
    return max(a,b);
}
int findSet(int x)
{
    if(x^p[x]) p[x]=findSet(p[x]);
    return p[x];
}
void MST()
{
    sort(a+1,a+1+m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=a[i].u,v=a[i].v,c=a[i].c,x=findSet(u),y=findSet(v);
        if(x==y) continue;
        e[++tot]=edge{v,c,f[u]},f[u]=tot;
        e[++tot]=edge{u,c,f[v]},f[v]=tot;
        mst+=c;
        p[x]=y;
    }
}
void dfs(int u,int par)
{
    fa[u][0]=par;
    dep[u]=dep[par]+1;
    for(int i=1;i<20;i++)
    {
        int pos=fa[u][i-1];
        Max[u][i]=max(Max[u][i-1],Max[pos][i-1]);
        sub[u][i]=max(sub[u][i-1],sub[pos][i-1]);
        fa[u][i]=fa[pos][i-1];
        if(Max[u][i-1]^Max[pos][i-1])
            sub[u][i]=max(sub[u][i],min(Max[u][i-1],Max[pos][i-1]));
    }
    for(int i=f[u];i;i=e[i].next)
        if(e[i].v^par)
        {
            Max[e[i].v][0]=e[i].c;
            sub[e[i].v][0]=-inf;
            dfs(e[i].v,u);
        }
}
void updata(int &x,int u,int i,int lim)
{
    x=op(x,Max[u][i],lim);
    x=op(x,sub[u][i],lim);
}
int lca(int u,int v,int lim)
{
    int res=-inf;
    for(int i=19;i>=0;i--)
    {
        if(dep[fa[u][i]]>=dep[v]) updata(res,u,i,lim),u=fa[u][i];
        if(dep[fa[v][i]]>=dep[u]) updata(res,v,i,lim),v=fa[v][i];
    }
    if(u==v) return res;
    for(int i=19;i>=0;i--)
        if(fa[u][i]^fa[v][i])
        {
            updata(res,u,i,lim);updata(res,v,i,lim);
            u=fa[u][i],v=fa[v][i];
        }
    updata(res,u,0,lim);updata(res,v,0,lim);
    return res;
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),c=read();
        a[i]=node{u,v,c};
    }
    MST();
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int val=lca(a[i].u,a[i].v,a[i].c);
        if(val!=-inf) ans=min(ans,a[i].c-val);
    }
    printf("%lld\n",ans+mst);
}

tips

1、lca做二进制分解是要从大到小。

2、注意要开long long。

3、极大值用(1<<62)。