[BJWC2010]严格次小生成树

首先考虑要严格小于，贪心地考虑就是一次加边删边，删去一条较小的边，然后加入一条较大的边。

\(\operatorname {Q_1}:\) 为什么是一次加边删边，难道不也可以多次吗？

哪怕多次，实际上加边和删边都可以一一匹配，\(x\) 次操作可以当做求第 \(x+1\) 小生成树。

朴素地枚举每条 原本未在生成树中的边，考虑将其加入，你需要找到形成的环中小于自己的边权的最大的边权。

也就是前驱。

考虑到每次查询的是一条路径上的前驱。

可以树剖加主席树获得两只 log 的做法。

写了一个大常数 \(\log^2\)，最后一个点死都卡不过去。

有几个问题也暴露出来了：

\(1.\) 不少数据结构题我在想到做法之后就基本不会继续考虑题目本身，而是直接去考虑代码实现了，以至于用错误复杂度的方法写半天。

\(2.\) 并查集经常忘记路径压缩。（自从 怎样更有力气 那道题开始就经常犯这个错误）

虽然并查集没路径压缩并没有影响我的运行时间？

以下是放弃了卡常的 \(90\) 分代码，运用了主席树可以跑两次求前驱的原理（和 Rui_R 口胡出来的）。

#include <stdio.h>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;
const int N=1e5+3;
const int M=3e5+3;
int n,m;
inline void jh(int &x,int &y){x^=y^=x^=y;return;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}

struct Rin
{
    char c;
    inline char gc()
    {
        static char rea[M];
        static char *head,*tail;
        return head==tail&&(tail=(head=rea)+fread(rea,1,M,stdin),head==tail)?EOF:*head++;
    }
    inline Rin&operator >>(int &x)
    {
        x=0;
        bool bj=false;
        for(c=gc();c>‘9‘||c<‘0‘;c=gc())if(c==‘-‘){c=gc();bj=true;break;}
        for(;c>=‘0‘&&c<=‘9‘;c=gc())x=(x<<1)+(x<<3)+(c^‘0‘);
        if(bj)x=-x;
        return *this;
    }
    inline Rin&operator <<(LL x)
    {
        static char a[66];
        static int tail;
        if(!x)putchar(48);
        else
        {
            tail=0;
            if(x<0){x=-x;putchar(‘-‘);}
            for(;x;x/=10)a[++tail]=x%10;
            for(;tail;tail--)putchar(a[tail]+48);
        }
        putchar(‘\n‘);
        return *this;
    }
}rin;

int F[N];
inline int find(int x){return (F[x]==x)?(x):(F[x]=find(F[x]));}

struct cow
{
    int y,z;
    cow(int y_,int z_){y=y_;z=z_;return;}
};
vector<cow>to[N];

struct milk
{
    int x,y,z;
    bool bj;
    inline void add(){to[x].push_back(cow(y,z));to[y].push_back(cow(x,z));bj=true;return;}
}a[M];
int c[M];
int psc;
inline bool myru_a(milk x,milk y){return x.z<y.z;}
inline bool myru_b(int x,int y){return a[x].z<a[y].z;}

struct zjj
{
    int ls,rs;
    int s;
}t[N*25];
int st[N];
int cutt;
inline void make_tree(int l,int r,int i)
{
    t[i].ls=t[i].rs=t[i].s=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    make_tree(l,mid,t[i].ls=++cutt);
    make_tree(mid+1,r,t[i].rs=++cutt);
    return;
}
inline void add_tree(int l,int r,int now,int last,int s)
{
    t[now]=t[last];t[now].s++;
    if(!t[now].ls)return;
    int mid=(l+r)>>1;
    if(mid>=s)add_tree(l,mid,t[now].ls=++cutt,t[last].ls,s);
    else add_tree(mid+1,r,t[now].rs=++cutt,t[last].rs,s);
    return;
}

struct prpr
{
    int fa;
    int dep;
    int top;
}T[N];
int num[N];
int son[N];
int lar[N];
int val[N];

int nam;
inline void dfs_down(int now,int fa)
{
    lar[now]=1;
    int maxl=0;
    for(int i=to[now].size()-1;i>=0;i--)
    {
        int y=to[now][i].y,z=to[now][i].z;
        if(y==fa)continue;
        val[y]=z;dfs_down(y,now);lar[now]+=lar[y];
        if(lar[y]>maxl)son[now]=y;
    }
    return;
}
inline void add_list(int now){T[nam+1].fa=num[now];T[nam+1].dep=T[num[now]].dep+1;return;}
inline void make_list(int now,int fa)
{
    num[now]=++nam;
    add_tree(1,psc,st[nam]=++cutt,st[nam-1],val[now]);
    T[nam].top=num[fa];
    if(!son[now])return;
    add_list(now);make_list(son[now],fa);
    for(int i=to[now].size()-1;i>=0;i--)if(!num[to[now][i].y])add_list(now),make_list(to[now][i].y,to[now][i].y);
    return;
}

inline int cheak_rank(int l,int r,int now,int last,int v)
{
    if(t[now].s-t[last].s==0)return 0;
    if(r<v)return t[now].s-t[last].s;
    if(l>=v)return 0;
    int mid=(l+r)>>1;
    if(mid<v)return t[t[now].ls].s-t[t[last].ls].s+cheak_rank(mid+1,r,t[now].rs,t[last].rs,v);
    else return cheak_rank(l,mid,t[now].ls,t[last].ls,v);
}
inline int cheak_num(int l,int r,int now,int last,int s)
{
    if(!t[now].ls)return c[l];
    int now_s=t[t[now].ls].s-t[t[last].ls].s;
    int mid=(l+r)>>1;
    if(now_s>=s)return cheak_num(l,mid,t[now].ls,t[last].ls,s);
    else return cheak_num(mid+1,r,t[now].rs,t[last].rs,s-now_s);
}
inline int cheak_(int l,int r,int v){return cheak_num(1,psc,st[r],st[l-1],cheak_rank(1,psc,st[r],st[l-1],v));}
inline int work(int now)
{
    int x=num[a[now].x],y=num[a[now].y];
    int sum=-0x3f3f3f3f;
    for(;T[x].top!=T[y].top;)
    {
        if(T[T[x].top].dep<T[T[y].top].dep)jh(x,y);
        sum=max(sum,cheak_(T[x].top,x,a[now].z));
        x=T[T[x].top].fa;
    }
    if(T[x].dep<T[y].dep)jh(x,y);
    if(x!=y)sum=max(sum,cheak_(y+1,x,a[now].z));
    return c[a[now].z]-sum;
}
int main()
{
    int i,j;
    rin>>n>>m;
    for(i=1;i<=m;i++){rin>>a[i].x>>a[i].y>>a[i].z;a[i].bj=false;}
    sort(a+1,a+m+1,myru_a);
    for(i=1;i<=m;i=j){c[++psc]=a[i].z;for(j=i;j<=m&&a[j].z==c[psc];j++)a[j].z=psc;}
    LL ans=0;
    for(i=1;i<=n;i++)F[i]=i;
    for(i=1;i<=m;i++)if(find(a[i].x)!=find(a[i].y))F[find(a[i].x)]=find(a[i].y),a[i].add(),ans+=c[a[i].z];
    make_tree(1,psc,st[0]=++cutt);
    dfs_down(1,0);T[1].dep=1;make_list(1,1);
    int mins=0x3f3f3f3f;
    for(i=m;i>=1;i--)if(!a[i].bj)if(c[a[i].z]-c[a[i].z-1]<mins)mins=min(mins,work(i));
    ans+=mins;
    rin<<ans;
    return 0;
}

然后的话，有一个双 log 的小常数做法（去查前驱真的好傻），加了一个最优性剪枝，开了 O2 过去了。

#include <stdio.h>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;
const int N=1e5+3;
const int M=3e5+3;
int n,m;
inline void jh(int &x,int &y){x^=y^=x^=y;return;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}

struct Rin
{
    char c;
    inline char gc()
    {
        static char rea[M];
        static char *head,*tail;
        return head==tail&&(tail=(head=rea)+fread(rea,1,M,stdin),head==tail)?EOF:*head++;
    }
    inline Rin&operator >>(int &x)
    {
        x=0;
        bool bj=false;
        for(c=gc();c>‘9‘||c<‘0‘;c=gc())if(c==‘-‘){c=gc();bj=true;break;}
        for(;c>=‘0‘&&c<=‘9‘;c=gc())x=(x<<1)+(x<<3)+(c^‘0‘);
        if(bj)x=-x;
        return *this;
    }
    inline Rin&operator <<(LL x)
    {
        static char a[66];
        static int tail;
        if(!x)putchar(48);
        else
        {
            tail=0;
            if(x<0){x=-x;putchar(‘-‘);}
            for(;x;x/=10)a[++tail]=x%10;
            for(;tail;tail--)putchar(a[tail]+48);
        }
        putchar(‘\n‘);
        return *this;
    }
}rin;

int F[N];
inline int find(int x){return (F[x]==x)?(x):(F[x]=find(F[x]));}

struct cow
{
    int y,z;
    cow(int y_,int z_){y=y_;z=z_;return;}
};
vector<cow>to[N];

struct milk
{
    int x,y,z;
    bool bj;
    inline void add(){to[x].push_back(cow(y,z));to[y].push_back(cow(x,z));bj=true;return;}
}a[M];
int c[M];
int nam;
inline bool myru_a(milk x,milk y){return x.z<y.z;}
inline bool myru_b(int x,int y){return a[x].z<a[y].z;}

struct prpr
{
    int fa;
    int dep;
    int top;
}T[N];
int num[N];
int son[N];
int lar[N];
int val[N];
inline void dfs_down(int now,int fa)
{
    lar[now]=1;
    int maxl=0;
    for(int i=to[now].size()-1;i>=0;i--)
    {
        int y=to[now][i].y,z=to[now][i].z;
        if(y==fa)continue;
        val[y]=z;dfs_down(y,now);lar[now]+=lar[y];
        if(lar[y]>maxl)son[now]=y;
    }
    return;
}
inline void add_list(int now){T[nam+1].fa=num[now];T[nam+1].dep=T[num[now]].dep+1;return;}
inline void make_list(int now,int fa)
{
    num[now]=++nam;
    T[nam].top=num[fa];
    if(!son[now])return;
    add_list(now);make_list(son[now],fa);
    for(int i=to[now].size()-1;i>=0;i--)if(!num[to[now][i].y])add_list(now),make_list(to[now][i].y,to[now][i].y);
    return;
}

struct zjj
{
    int l,r;
    int ls,rs;
    int f;
}t[N<<1];
inline void make_tree(int l,int r,int i)
{
    t[i].l=l;t[i].r=r;
    t[i].ls=t[i].rs=t[i].f=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    make_tree(l,mid,t[i].ls=++nam);
    make_tree(mid+1,r,t[i].rs=++nam);
    return;
}
inline void add(int x,int y,int i)
{
    t[i].f=max(t[i].f,y);
    if(t[i].l==t[i].r)return;
    if(t[t[i].ls].r>=x)add(x,y,t[i].ls);
    if(t[t[i].rs].l<=x)add(x,y,t[i].rs);
    return;
}
inline void add_(int x,int y,int z){x=num[x];y=num[y];x=(T[x].dep>T[y].dep)?(x):(y);add(x,c[z],1);return;}
inline int cheak(int l,int r,int i)
{
    if(l<=t[i].l&&t[i].r<=r)return t[i].f;
    int ans=0;
    if(t[t[i].ls].r>=l)ans=max(ans,cheak(l,r,t[i].ls));
    if(t[t[i].rs].l<=r)ans=max(ans,cheak(l,r,t[i].rs));
    return ans;
}
inline int work(int now)
{
    int x=num[a[now].x],y=num[a[now].y];
    int sum=-0x3f3f3f3f;
    for(;T[x].top!=T[y].top;)
    {
        if(T[T[x].top].dep<T[T[y].top].dep)jh(x,y);
        sum=max(sum,cheak(T[x].top,x,1));
        x=T[T[x].top].fa;
    }
    if(x<y)jh(x,y);
    if(x!=y)sum=max(sum,cheak(y+1,x,1));
    return c[a[now].z]-sum;
}

int main()
{
    int i,j;
    rin>>n>>m;
    for(i=1;i<=m;i++){rin>>a[i].x>>a[i].y>>a[i].z;a[i].bj=false;}
    sort(a+1,a+m+1,myru_a);
    for(i=1;i<=m;i=j){c[++nam]=a[i].z;for(j=i;j<=m&&a[j].z==c[nam];j++)a[j].z=nam;}nam=0;
    LL ans=0;
    for(i=1;i<=n;i++)F[i]=i;
    for(i=1;i<=m;i++)if(find(a[i].x)!=find(a[i].y))F[find(a[i].x)]=find(a[i].y),a[i].add(),ans+=c[a[i].z];
    dfs_down(1,0);T[1].dep=1;make_list(1,1);

    nam=0;make_tree(1,n,++nam);
    int mins=0x3f3f3f3f;
    for(i=1;i<=m;i=j)
    {
        for(j=i;j<=m&&a[j].z==a[i].z;j++)if(!a[j].bj)if(c[a[j].z]-c[a[j].z-1]<mins)mins=min(mins,work(j));
        for(j=i;j<=m&&a[j].z==a[i].z;j++)if(a[j].bj)add_(a[j].x,a[j].y,a[j].z);
    }
    ans+=mins;
    rin<<ans;
    return 0;
}

[BJWC2010]严格次小生成树

原文：https://www.cnblogs.com/zjjws/p/14008058.html