题目传送门

题意:

给定一张无向图$G(V,E)$,若图上的最小生成树的边集为$E_M$,边$e$的权值为$value(e)$,求找到一个边集为$E_s$的严格次小生成树满足:

$\sum_{e\in E_m}value(e)<\sum_{e\in E_s}value(e)$且$\sum_{e\in E_s}value(e)$最小。

$1\leq N \leq 100000,1\leq M \leq 300000,0\leq value(e)\leq 10^9$


前排提示:最终选择的是$Kruskal$求最小生成树。

这数据够恶心不愧是紫题

Round 1

如果不要求严格,普通的次小生成树要怎么求呢?

先在图中找到最小生成树,然后枚举每一条没有加入最小生成树的边$(u,v)$,并将其加入生成树。此时$(u,v)$间必定成环,还要最优的话就在原来$u->lca(u,v)->v$上删掉原有的一条最大权值的边即可。枚举所有这样的边之后取得最优即可。

当然,不是一定要这样模拟出来,考虑用一个数组$mx1[i][j]$表示$(i,j)$之间的最大边,在求得最小生成树的过程中顺路维护一下就$ok$了。


Round 2

它为什么不严格?

我们枚举未加入生成树的边$(u,v)$的权值$w$,可能会等于$u,v$之间的最大边

什么?你说如果相等就跳过?我当初也这么想

就算$w$等于最大边,$(u,v)$间的次大边也可能影响答案。


Round 3

如何让它从不严格变得严格?

暴力地考虑再维护一个两点间的次大边$mx2[i][j]$表示$(i,j)$之间的次大值,发现在最小生成树过程中难以维护。

考虑优雅地暴力——倍增

修改一下定义。我们用$mx1[i][j]$表示节点$i$到它的$2^j$级父亲间路径边权的最大值,$mx2$则是次小值。

于是就可以在$O(nlogn)$内用倍增维护。

那么如何尝试把一条边加进去呢?分成$(u→lca(u,v))$,$(v→lca(u,v))$两段,分别在路上找到最大值。如果最大值等于了选定边的权值,那就选择次大值


Round 4

最后是一些小细节的处理。

极大值需要超过$2^{31}$,不然会炸。

因为$Kruskal$需要对边排序,所以把原图和用来跑倍增的最小生成树分开。

并查集日常按秩合并+路径压缩,再加上一点点小卡常就不会因为评测姬波动而超时了。其实只是因为我#define int long long的垃圾习惯。

所以注意合适地开long long

初始值$mx1[v][0]=val[i],mx2[v][0]=-INF$(点$v$由边$i$搜到)。


Round 5

代码部分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
const int INF=19260817123456;
struct node{int u,v,w;}g[N<<3];
int cnt,to[N<<3],val[N<<3],nxt[N<<3],head[N<<3];
int n,m;
int fa[N],sz[N];
int dep[N];
int pa[N][25];
int mx1[N][25];
int mx2[N][25];
bool used[N<<3];
void add(int u,int v,int w)
{
    cnt++;
    to[cnt]=v,val[cnt]=w,nxt[cnt]=head[u];
    head[u]=cnt;
}
inline int read()
{
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
inline bool cmp(node a,node b){return a.w<b.w;}
inline int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline void dfs(int u,int f)
{
    dep[u]=dep[f]+1;
    pa[u][0]=f;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==f)continue;
        mx1[v][0]=val[i];
        mx2[v][0]=-INF;
        dfs(v,u);
    }
}

void init()
{
    for(int i=1;i<=18;i++)
        for(int u=1;u<=n;u++)
        {
            pa[u][i]=pa[pa[u][i-1]][i-1];
            
            mx1[u][i]=max(mx1[u][i-1],mx1[pa[u][i-1]][i-1]);
            mx2[u][i]=max(mx2[u][i-1],mx2[pa[u][i-1]][i-1]);
            
            if(mx1[u][i-1]>mx1[pa[u][i-1]][i-1])
                mx2[u][i]=max(mx2[u][i],mx1[pa[u][i-1]][i-1]);
            else if(mx1[u][i-1]<mx2[pa[u][i-1]][i-1])
                mx2[u][i]=max(mx2[u][i],mx1[u][i-1]);
        }
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])
        x=pa[x][(int)log2(dep[x]-dep[y])];
    if(x==y)return x;
    for(int i=(int)log2(dep[x]);~i;i--)
        if(pa[x][i]!=pa[y][i])
            x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
inline int tries(int u,int v,int w)
{
    int tmp=-INF;
    for(int i=18;~i;i--)
        if(dep[pa[u][i]]>=dep[v])
        {
            if(w!=mx1[u][i])tmp=max(tmp,mx1[u][i]);
            else tmp=max(tmp,mx2[u][i]);
            v=pa[v][i];
        }
    return tmp;
}
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++)
        g[i].u=read(),g[i].v=read(),g[i].w=read();
    sort(g+1,g+1+m,cmp);
    int tot=0,sum=0;
    for(int i=1;i<=m;i++)
    {
        int r1=get(g[i].u),r2=get(g[i].v),w=g[i].w;
        if(r1==r2)continue;
        if(sz[r1]>sz[r2])fa[r2]=r1,sz[r1]+=sz[r2];
        else fa[r1]=r2,sz[r2]+=sz[r1];
        sum+=w,tot++,used[i]=1;
        add(g[i].u,g[i].v,w);
        add(g[i].v,g[i].u,w);
        if(tot==n-1)break;
    }
    mx2[1][0]=-INF;
    dep[1]=1;
    dfs(1,0);
    init();
    int ans=INF;
    for(int i=1;i<=m;i++)
    {
        if(used[i])continue;
        int u=g[i].u,v=g[i].v,w=g[i].w;
        int k=lca(u,v);
        ans=min(ans,sum-max(tries(u,k,w),tries(v,k,w))+w);
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 07 月 30 日 07 : 31 PM