Luogu5633 最小度限制生成树

题面

简化题意

求一个最小生成树，满足 $s$ 的度恰好为 $k$。

$n\leq 5\times10^4,m\leq 10^5$。

题解

我们考虑朴素地用 kruskal 构造一个生成树，是按照边权加边的。这种方法显然无法保证 $s$ 的度。

考虑将 $s$ 相接的边权修改一下，使得最后生成树能让 $s$ 有这个度数。

考虑 wqs 二分一个 $\Delta$，每次让 $s$ 相邻的边权都加上 $\Delta$，然后跑朴素的 kruskal。

根据直觉，若 $s$ 的度多于限制，就增加边权，更少则反之。注意判断一下无解的情况：

• 不连通。
• $s$ 的度不到 $k$。
• 二分的 $\Delta$ 不能让 $s$ 的度达到 $k$。

显然前两种情况用第三种情况判也没有问题。

---

然而上述做法会 TLE。考虑假设二分的值域大小为 $a$，则复杂度为 $n\log n\log a$ 的。

然而，由于每次只修改了与 $s$ 相邻的边，直接把这类边单独提出来。两边分别排序。注意到这是不需要放回来重新排序的，可以用归并的思想，每次判断此时是第一类小还是第二类小加进去。

复杂度 $m\log a$。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=50004,max_m=500005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0){// 懒，直接在快写里面判无解
        puts("Impossible");
        return;
    }
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m,s,k,m1,m2;

struct edge{
    int u,v,w;
    bool operator < (const edge &b) const{
        edge a=*this;
        return a.w<b.w;
    }
}e1[max_m],e2[max_m]; // e1 一类边；e2 二类边
inline edge makee(int x,int y,int z){
    edge res;
    res.u=x,res.v=y,res.w=z;
    return res;
}

struct par{ // 习惯，手写 pair
    int x,y;
};
inline par makep(int x,int y){
    par res;
    res.x=x,res.y=y;
    return res;
}

struct Union{
    int fa[max_n],sz[max_n],n;
    inline void init(int x){
        n=x;
        for(register int i=1;i<=n;++i)
            fa[i]=i,sz[i]=1;
    }
    inline int find(int x){
        if(x==fa[x]) return x;
        return fa[x]=find(fa[x]);
    }
    inline bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y) return 0;
        if(sz[x]>sz[y]) x^=y^=x^=y;
        sz[y]+=sz[x],fa[x]=y;
        return 1;
    }
}uf;

inline par check(int mid){ // kruscal
    if(mid) for(register int i=1;i<=m1;++i)
        e1[i].w+=mid;
    uf.init(n);
    int res1=0,res2=0;
    for(register int i=1,j1=1,j2=1;i<n;){
        if(j1>m1 && j2>m2 && i<n-1) // 两种边都用完了，还没有选够，说明图不连通，无解
            return makep(-1,-1);
        if(j1<=m1 && (j2>m2 || e1[j1].w<=e2[j2].w)){ // 选 1 类
            int u=e1[j1].u,v=e1[j1].v;
            if(uf.merge(u,v)){
                ++res1,res2+=e1[j1].w,
                ++i;
            }
            ++j1;
        }
        else if(j2<=m2 || j1>m1){ // 选 2 类
            int u=e2[j2].u,v=e2[j2].v;
            if(uf.merge(u,v)){
                res2+=e2[j2].w,
                ++i;
            }
            ++j2;
        }
    }
    if(mid) for(register int i=1;i<=m1;++i)
        e1[i].w-=mid;
    return makep(res1,res2-res1*mid);
}// res1：s 的度，res2：最小生成树大小，记得减去偏移量

inline int erfen(int l,int r){
    --l,++r;int ans=0;
    while(l<r-1){
        int mid=(l+r)>>1;par res=check(mid);
        if(res.x==k)
            l=mid,ans=mid;
        else if(res.x<k)
            r=mid;
        else
            l=mid;
    }
    par res=check(ans);
    if(res.x!=k) return -1; // 最后二分到的答案无解
    return res.y;
}

signed main(){
//  freopen(".in","r",stdin),
//  freopen(".out","w",stdout);
    n=read(),m=read(),s=read(),k=read();
    for(register int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        if(u==s || v==s)
            e1[++m1]=makee(u,v,w);
        else
            e2[++m2]=makee(u,v,w);
    }
    sort(e1+1,e1+1+m1),sort(e2+1,e2+1+m2);
    write(erfen(-30000,30000));
    return 0;
}