洛谷P5633 最小度限制生成树 题解

题目链接：P5633 最小度限制生成树

题意：

给你一个有 \(n\) 个节点，\(m\) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 \(s\) 的节点正好连了 \(k\) 条边。

可能会出现无解的情况，如果无解，则输出 Impossible。

对于 \(100\%\) 的数据，\(1\leq n \le 5\times 10^4\)，\(1\leq m \le 5\times 10^5\)，\(1\leq k \le 100\)，\(0\leq w\leq 3\times 10^4\)。

如果做过这道题应该会觉得很简单了

我们把与 \(s\) 相连的所有边标记为白边，其他边为黑边

然后问题就转化为了选恰好 \(k\) 条白边的最小花费

考虑wqs二分，最好用归并优化一下

这题的难点在无解的情况如何判断

• 白边不够用，如果与 \(s\) 相连的边小于 \(k\) 条，无解

• 黑边不够用，也就是生成树不得不包括大于 \(k\) 条白边，无解

时间复杂度 \(O(n\log n + n\log {\max\{w_i\}})\)

可以通过所有的hack数据，请放心食用 qwq

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*_p1,*_p2;
    char readchar()
    {
        if(_p1==_p2)_p1=buf1,_p2=buf1+fread(buf1,1,SIZ,stdin);
        return _p1==_p2?EOF:*_p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO; 
#define N (int)(5e4+15)
#define M (int)(5e5+15)

int n,m,s,k,p1,p2,cnt,sum,mx,f[N];
struct Edge{int u,v,w,c;}e[M],c1[M],c2[M];
void init(){for(int i=1; i<=n; i++)f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int cmp(Edge a,Edge b){return a.w<b.w;}
int merge(int u,int v)
{
    u=find(u);v=find(v);
    if(u==v)return 0;
    return f[u]=v,1;
}
void proc(int mid)
{
    for(int d=1; d<=p1; d++)
        c1[d].w-=mid;
    int i=1,j=1,pos=0;
    for(; i<=p1; i++)
    {
        while(c1[i].w>c2[j].w&&j<=p2)
            e[++pos]=c2[j++];
        e[++pos]=c1[i];
    }
    while(j<=p2)e[++pos]=c2[j++];
    for(int d=1; d<=p1; d++)
        c1[d].w+=mid;
}
void kruskal(int mid)
{
    proc(mid); cnt=sum=0;
    int tmp=0; init();
    for(int i=1; i<=m&&tmp<n; i++)
        if(merge(e[i].u,e[i].v))
        {
            cnt+=e[i].c;
            sum+=e[i].w;++tmp;
        }
}
signed main()
{
    read(n);read(m);read(s);read(k);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        if(u==s||v==s) 
            c1[++p1]={u,v,w,1},mx=max(mx,w);
        else c2[++p2]={u,v,w,0};
    }
    if(p1<k)return puts("Impossible"),0;
    sort(c1+1,c1+p1+1,cmp);sort(c2+1,c2+p2+1,cmp);
    int l=-mx-5,r=mx+5;
    kruskal(l); if(cnt>k)return puts("Impossible"),0;
    while(l<r)
    {
        int mid=(l+r)>>1;
        kruskal(mid);
        if(cnt>=k) r=mid;
        else l=mid+1;
    }
    kruskal(l); write(sum+k*l);
    return 0;
}