洛谷4180 严格次小生成树

题解 图论-最小生成树 数据结构-树链剖分 省选/NOI-
题目链接 编辑文章

这道题做法还是比较容易想到的,就是码量有点大。

不严格次小生成树的思路就是先得到最小生成树,然后枚举每一条不在树里的边,找到所构成的环上权值最大的边替换掉。

而这道题要求严格次小,那么权值最大的边就不能与枚举的边权值相同,如果相同就替换环上次大的边即可。

我还是敲了树剖,对于最大和次大边我用pair来存,可能是STL的缘故不开O2只有90。在合并(线段树合并和lca两侧合并)时对最大和次大的处理如下:

inline pr get_max(pr x,pr y)
{
    pr ans=mp(0,0);
    if (x.first==y.first)
    {
        ans.first=x.first;
        ans.second=max(x.second,y.second);
    }
    else
    {
        ans.first=max(x.first,y.first);
        ans.second=max(max(x.second,y.second),min(x.first,y.first));
    }
    return ans;
}

思路就是如果最大值相同那么次大值就从两个次大值里面选;否则最大值取两个最大值里面最大,次大值从剩下三个里面选最大。

需要注意的是要开long long,还有答案可能超过 $10^{9}$ ,所以inf取 $1e9$ 是不够的。还有要开O2

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define mp make_pair

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge{
    ll next,to,w;
} edge[200005];
struct Edge2{
    ll st,ed,w;
} edge2[300005];
struct Tree{
    ll left,right;
    pr mx;
} tree[400005];
bool intree[300005];
ll n,m,a,b,c,cnt,dfsord,head[100005],fa[100005],son[100005],top[100005],siz[100005],deep[100005],id[100005],w[100005],wnew[100005],fath[100005];

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline pr get_max(pr x,pr y)
{
    pr ans=mp(0,0);
    if (x.first==y.first)
    {
        ans.first=x.first;
        ans.second=max(x.second,y.second);
    }
    else
    {
        ans.first=max(x.first,y.first);
        ans.second=max(max(x.second,y.second),min(x.first,y.first));
    }
    return ans;
}

inline void pushup(ll x) { tree[x].mx=get_max(tree[x*2].mx,tree[x*2+1].mx); }

void build(ll x,ll l,ll r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l==1) tree[x].mx.first=wnew[l];
    else
    {
        ll mid=(l+r)>>1;
        build(x*2,l,mid);
        build(x*2+1,mid,r);
        pushup(x);
    }
}

pr query(ll x,ll l,ll r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].mx;
    else
    {
        pr ans=mp(0,0);
        ll mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) ans=query(x*2,l,r);
        if (r>mid) ans=get_max(ans,query(x*2+1,l,r));
        return ans;
    }
}

void dfs1(ll x,ll f,ll dep)
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    ll mx=0;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==f) continue;
        w[y]=edge[i].w;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[y]>mx)
        {
            mx=siz[y];
            son[x]=y;
        }
    }
}

void dfs2(ll x,ll topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    wnew[dfsord]=w[x];
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline ll qRange(ll u,ll v,ll mx) // = ? mx2 : mx
{
    pr ans=mp(0,0);
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans=get_max(ans,query(1,id[top[u]],id[u]+1));
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    if (id[u]!=id[v]) ans=get_max(ans,query(1,id[u]+1,id[v]+1));
    return (ans.first==mx) ? ans.second : ans.first;
}

inline void init() { for (ll i=1;i<=n;i++) fath[i]=i; }

ll getfa(ll x) { return (x==fath[x]) ? x : fath[x]=getfa(fath[x]); }

inline bool merge(ll x,ll y)
{
    ll gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    fath[gfx]=fath[gfy];
    return 1;
}

inline bool cmp(Edge2 x,Edge2 y) { return x.w<y.w; }

int main()
{
    n=read(); m=read();
    init();
    for (ll i=1;i<=m;i++) edge2[i].st=read(),edge2[i].ed=read(),edge2[i].w=read();
    sort(edge2+1,edge2+m+1,cmp);
    ll ecnt=0,sum=0;
    for (ll i=1;i<=m;i++)
    {
        ll x=edge2[i].st,y=edge2[i].ed,z=edge2[i].w;
        if (!merge(x,y)) continue;
        add(x,y,z);
        add(y,x,z);
        intree[i]=1;
        ecnt++;
        sum+=z;
        if (ecnt==n-1) break;
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n+1);
    ll ans=1e18;
    for (ll i=1;i<=m;i++)
    {
        if (intree[i]) continue;
        ans=min(ans,sum-qRange(edge2[i].st,edge2[i].ed,edge2[i].w)+edge2[i].w);
    }
    printf("%lld",ans);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。