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

qwaszx · 2019-05-12 18:31:41 · 题解

可以证明次小生成树一定是最小生成树换一条边形成的，因为换更多的边一定不优

所以先跑出来一个最小生成树，然后枚举所有非树边，加入非树边之后会形成一个环，然后去掉环上的最大的一条树边

但是有一个问题是如果非树边等于环上的最大树边那么是不符合要求的，所以还要维护一个严格次大的树边

现在问题变成多次询问两点之间的最大和次大值.倍增是一种方法但是常数不优越

树剖一下，因为没有修改，所以还可以维护出每个点到链头的最大次大值，这样只需要最后查询一下即可.

最后这个查询可以线段树，这里用了玄学优化的ST表，期望O(n)的.可以去看lxl的blog.

最优解不知道写了个什么鬼算法能过，反正随便hack

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define INF 1000000007
using namespace std;
const int N=4e5;
struct Node{int mx,smx;}val[N];
int max(const int &a,const int &b){return a>b?a:b;}
int tp[N],f[N],dep[N],size[N],son[N],nxt[N],fst[N],mm,dfs_cnt,id[N],w[N],tw[N],n,m;
struct Edge{int u,v,w;}e1[N],e[N],tmp[N];
void ade(int u,int v,int w){e[++mm]=(Edge){u,v,w};nxt[mm]=fst[u],fst[u]=mm;}
void link(int u,int v,int w){ade(u,v,w),ade(v,u,w);}
Node pushup(const Node &a,const Node &b)
{
    if(a.mx>b.mx)return (Node){a.mx,max(a.smx,b.mx)};
    if(a.mx==b.mx)return (Node){a.mx,max(a.smx,b.smx)};
    return (Node){b.mx,max(a.mx,b.smx)};
}
Node pushup(const Node &a,const int &b)
{
    if(b>=a.mx)return (Node){b,a.smx};
    return (Node){a.mx,max(b,a.smx)};
}
struct DSU
{
    int f[N],size[N];
    void clear(){for(int i=1;i<=n;i++)size[i]=1;}
    int find(int x){return !f[x]?x:f[x]=find(f[x]);}
    void merge(int x,int y)
    {
        if(size[x]<size[y])f[x]=y,size[y]+=size[x];
        else f[y]=x,size[x]+=size[y];
    }
}dsu;
struct STable
{
    Node f[20][10000],pre[N],suf[N];
    int lg[N],blo,bl[N];
    void make()
    {
        blo=ceil(sqrt(n*4/3));
        for(register int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;int bln=bl[n];
        for(register int i=1;i<=bln;i++)
        {
            int l=(i-1)*blo+1,r=min(i*blo,n);
            pre[l]=(Node){w[l],-INF},suf[r]=(Node){w[r],-INF};
            for(register int j=l+1;j<=r;j++)pre[j]=pushup(pre[j-1],w[j]);
            for(register int j=r-1;j>=l;j--)suf[j]=pushup(suf[j+1],w[j]);
            f[0][i]=pre[r];
        }
        lg[1]=0;for(register int i=2;i<=bln;i++)lg[i]=lg[i>>1]+1;
        for(register int i=1;(1<<i)<=bln;i++)
            for(register int j=1;j+(1<<i)-1<=bln;j++)
                f[i][j]=pushup(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    }
    Node query(int l,int r)
    {
        int bll=bl[l],blr=bl[r];Node ans;
        if(bll==blr){ans=(Node){w[l],-INF};for(register int i=l+1;i<=r;i++)ans=pushup(ans,w[i]);return ans;}
        ans=pushup(suf[l],pre[r]);
        if(++bll<=--blr)
        {
            int len=lg[blr-bll+1];
            ans=pushup(ans,pushup(f[len][bll],f[len][blr-(1<<len)+1]));
        }
        return ans;
    }
}a;
void dfs1(int u,int fa)
{
    f[u]=fa,dep[u]=dep[fa]+1,size[u]=1;
    int mx=0;
    for(register int i=fst[u];i;i=nxt[i])
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>mx)mx=size[v],son[u]=v;
    }
}
void dfs2(register int u,int top)
{
    tp[u]=top,id[u]=++dfs_cnt;w[dfs_cnt]=tw[u];
    if(u==top)val[u]=(Node){tw[u],-INF};
    else val[u]=pushup(val[f[u]],tw[u]);
    if(son[u])dfs2(son[u],top);
    for(register int i=fst[u];i;i=nxt[i])
    {
        int v=e[i].v;
        if(v!=son[u]&&v!=f[u])
            dfs2(v,v);
    }
}
Node query(register int x,register int y)
{
    register Node ans={-INF,-INF};
    while(tp[x]!=tp[y])
    {
        if(dep[tp[x]]<dep[tp[y]])swap(x,y);
        ans=pushup(ans,val[x]);
        x=f[tp[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    if(x!=y)ans=pushup(ans,a.query(id[y]+1,id[x]));
    return ans;
}
int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int cmp(const Edge &a,const Edge &b){return a.w<b.w;}
int main()
{
    n=getin(),m=getin();
    for(register int i=1;i<=m;i++)
    {
        e1[i].u=getin(),e1[i].v=getin(),e1[i].w=getin();
    }
    sort(e1+1,e1+m+1,cmp);long long s=0,ans=1e18;int cnt=0;
    dsu.clear();//puts("");
    for(register int i=1;i<=m;i++)
    {
        int u=dsu.find(e1[i].u),v=dsu.find(e1[i].v);
        if(u!=v)
        {
            link(e1[i].u,e1[i].v,e1[i].w);
            dsu.merge(u,v);s+=e1[i].w;//cout<<e1[i].u<<" "<<e1[i].v<<" "<<e1[i].w<<endl;
        }
        else tmp[++cnt]=(Edge){e1[i].u,e1[i].v,e1[i].w};
    }
    dfs1(1,0);tw[1]=-INF;
    for(register int i=1;i<=mm;i+=2)
        tw[dep[e[i].u]>dep[e[i].v]?e[i].u:e[i].v]=e[i].w;
    dfs2(1,1);a.make();
    for(register int i=1;i<=cnt;i++)
    {
        int u=tmp[i].u,v=tmp[i].v,w=tmp[i].w;//cout<<u<<" "<<v<<endl;
        Node t=query(u,v);//printf("%d %d\n",t.mx,t.smx);
        if(w==t.mx)ans=min(ans,s-t.smx+w);
        else ans=min(ans,s-t.mx+w);
    }
    cout<<ans<<endl;
}