题解 P5633 【最小度限制生成树】

· · 题解

看到对一个特殊的点进行限制，我们不难想到用 wqs 二分进行计算。对所有连向 s 的边进行定量偏移，使所有连向 s 的边的边权 q 加上二分的定量 \Delta。这个问题就变成了一个可行性问题。

具体做法是，我们修改之后可以求出最小生成树，这个过程中我们显然可以计算连接到 s 的边有多少条。如果连接到 s 的边数大于等于 k，我们就提高下界；否则降低上界。接下来我们得到了一个准确的 \Delta，答案就是当前求出的最小生成树边权和再减去 k \times \Delta。

一些无解的情况：

这样还是会 T。考虑优化，我们每次将边排序的时候分两类（是否连接 s）排序，连接 s 的边优先级更高。然后跑 Kruskal 算法即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct UnionFindSet{
    LL fa[50005];
    void makeSet(LL upper){for(LL i=0;i<=upper;++i) fa[i]=i;}
    LL findSet(LL x)
    {
        if(x==fa[x])    return fa[x];
        return fa[x]=findSet(fa[x]);
    }
    void unionSet(LL x,LL y)
    {
        LL xx=findSet(x),yy=findSet(y);
        if(xx==yy)  return ;
        fa[xx]=yy;
    }
    bool bunionSet(LL x,LL y)
    {
        LL xx=findSet(x),yy=findSet(y);
        if(xx==yy)  return false;
        fa[xx]=yy;
        return true;
    }
}ufs;
struct Edge{
    LL u,v,val;
    Edge(){u=v=val=0;}
    Edge(LL U,LL V,LL va){u=U,v=V,val=va;}
    bool operator < (Edge another) const {return val<another.val;}
}e1[500005],e2[500005],g[500005];
LL n,m,s,t1,t2,valt;
void msort(LL delta)
{
    for(LL i=1;i<=t1;++i)   e1[i].val+=delta;
    LL i=1,j=1,k=0;
    while(i<=t2 && j<=t1)
    {
        if(e2[i]<e1[j]) g[++k]=e2[i++];
        else    g[++k]=e1[j++];
    }
    while(j<=t1)    g[++k]=e1[j++];
    while(i<=t2)    g[++k]=e2[i++];
    for(LL l=1;l<=t1;++l)   e1[l].val-=delta;
}
/*
void msort(int delta)
{
    for(int i=1;i<=t1;++i)  e1[i].val+=delta;
    int i=1,j=1,k=0;
    while(i<=t1 && j<=t2)
    {
        if(e1[i]<e2[j]) g[++k]=e1[i++];
        else    g[++k]=e2[j++];
    }
    while(i<=t1)    g[++k]=e1[i++];
    while(j<=t2)    g[++k]=e2[j++];
    for(int l=1;l<=t1;++l)  e1[i].val-=delta;
}
*/
LL k;
bool check(LL delta)
{
    msort(delta);
    LL cnt=0;
    valt=0;
    ufs.makeSet(n);
    LL blk=n;
    for(LL i=1;i<=m;++i)
    {
        if(!ufs.bunionSet(g[i].u,g[i].v))   continue;
        cnt+=LL(g[i].u==s || g[i].v==s);
        valt+=g[i].val;
        --blk;
        if(blk<=1)  break;
    }
    return cnt>=k;
}
bool specialCheck(LL delta)
{
    msort(delta);
    LL cnt=0;
    valt=0;
    ufs.makeSet(n);
    LL blk=n;
    for(LL i=1;i<=m;++i)
    {
        if(!ufs.bunionSet(g[i].u,g[i].v))   continue;
        cnt+=LL(g[i].u==s || g[i].v==s);
        valt+=g[i].val;
        --blk;
        if(blk<=1)  break;
    }
    return cnt==k;
}
//bool check(LL delta)
//{
//  msort(delta);
//  ufs.makeSet(n);
//  LL cnt=0;
//  valt=0;
//  for(LL i=1;i<=m;++i)
//  {
//      if(ufs.bunionSet(g[i].u,g[i].v))
//      {
//          if(g[i].u==s || g[i].v==s)  ++cnt;
//          valt+=g[i].val;
//      }
//  }
//  printf("%d\n",cnt);
//  return cnt>=k;
//}
int main(){
    scanf("%lld %lld %lld %lld",&n,&m,&s,&k);
    for(LL i=1;i<=m;++i)
    {
        LL u,v,val;
        scanf("%lld %lld %lld",&u,&v,&val);
        if(u==s || v==s)    e1[++t1]=Edge(u,v,val);
        else    e2[++t2]=Edge(u,v,val);
    }
    if(t1<k)    return puts("Impossible")&0;
    ufs.makeSet(n);
    LL blk=n;
    for(LL i=1;i<=t1;++i)   blk-=ufs.bunionSet(e1[i].u,e1[i].v);
    for(LL i=1;i<=t2;++i)   blk-=ufs.bunionSet(e2[i].u,e2[i].v);
    if(blk!=1)  return puts("Impossible")&0;
    sort(e1+1,e1+1+t1);
    sort(e2+1,e2+1+t2);
    LL l=-10000000ll,r=10000000ll,ans=-10000000ll;
    if(!check(l))   return puts("Impossible")&0;
    while(l<=r)
    {
        LL mid=(l+r)>>1;
        if(check(mid))  l=mid+1,ans=mid;
        else    r=mid-1;
    }
    check(ans);
    if(!specialCheck(ans))  return puts("Impossible")&0;
    printf("%lld",valt-k*ans);
    return 0;
}