\(ProblemLink\)

题目大意

求一种特殊的最小生成树。给定一个有\(n\)个节点和\(m\)条边的图，找出一个生成树满足从根节点\(1\)直接连向其余节点的边要恰好是\(k\)条，在此条件下生成树的权值和最小。

思路分析

根据我们带权二分的经验，我们会发现，我们可以给与1相连的边给一个附加权值。

显然，权值越大，选的边就越少。

于是我们就可以二分这个权值。

根据我们\(wqs\)二分的经验，可能并不能刚好二分到那个点，斜率可能一样。

这个时候，我们就枚举在生成树外的边\((u,v)\),设权值为\(w\)

找到\(u,v\)分别属于的与1相连的连通块的根\(u',v'\)

如果\(w=(1,u'/v')\)就替换。

为什么一定要恰好相等才替换？

事实上就是那些边权相等的边导致1的度数超过了\(k\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
#define RG register
#define gi geti<int>()
#define gl geti<ll>()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>
IL T geti()
{
    RG T xi=0;
    RG char ch=gc;
    bool f=0;
    while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
    while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
const int N=1e4+7,M=1e5+7;
struct edge{
    int u,v,w,id;
    bool operator < (const edge &b)const{return w==b.w?u<b.u:w<b.w;}
}e[M];
vector<edge>G[N];
int edgecnt;
int fa[N],rk[N];
bitset<100001>vis;
int n,m,k,cnt;
inline void clear(){for(int i=1;i<=n;++i)fa[i]=i;fill(rk,rk+N,1);}
inline int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}
inline bool merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return 0;
    if(rk[x]>rk[y])swap(x,y);
    fa[x]=y,rk[y]+=rk[x];
    return 1;
}
inline bool check()
{
    clear();
    int deg=0;
    for(int i=1;i<=m;++i)
        if(e[i].u!=1)merge(e[i].u,e[i].v);
        else ++deg;
    if(deg<k)return 0;
    cnt=0;
    for(int i=2;i<=n;++i)
        if(find(i)==i)
            ++cnt;
    if(cnt>k)return 0;
    for(int i=1;i<=m;++i)
        if(e[i].u==1)
            merge(e[i].u,e[i].v);
    cnt=0;
    for(int i=1;i<=n;++i)
        if(find(i)==i)
            ++cnt;
    return cnt==1;
}
inline void dfs(int x,int p)
{
    fa[x]=fa[p];
    for(auto &&i:G[x])
        if(i.v^p)dfs(i.v,x);
}
int val[N],id[N];
set<int>print;
int main(void)
{
    #ifndef ONLINE_JUDGE
//  File("");
    #endif
    n=gi,m=gi,k=gi;
    if(n==1)return pi(0),0;
    int maxw=0;
    for(int i=1;i<=m;++i)
    {
        e[i]=(edge){gi,gi,gi,i};
        if(e[i].u>e[i].v)swap(e[i].u,e[i].v);
        chkmax(maxw,e[i].w);
    }
    sort(e+1,e+m+1);
    if(!check())return pi(-1),0;
    int l=-maxw,r=maxw,ans=998244353;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        clear();
        for(int i=1;i<=m;++i)
            if(e[i].u==1)
                e[i].w+=mid;
        sort(e+1,e+m+1);
        cnt=0;
        for(int i=1,tot=0;i<=m;++i)
            if(merge(e[i].u,e[i].v))
            {
                ++tot;
                if(e[i].u==1)++cnt;
                if(tot==n-1)break;
            }
        for(int i=1;i<=m;++i)
            if(e[i].u==1)
                e[i].w-=mid;
        if(cnt>=k)ans=mid,l=mid+1;
        else r=mid-1;
    }
//  cout<<"Val=:"<<ans<<endl;
    clear(),cnt=0;
    for(int i=1;i<=m;++i)
        if(e[i].u==1)
            e[i].w+=ans;
    sort(e+1,e+m+1);
    for(int i=1;i<=m;++i)
        if(merge(e[i].u,e[i].v))
        {
            vis.set(i);
            if(e[i].u==1)++cnt;
            print.insert(e[i].id);
            G[e[i].u].push_back((edge){0,e[i].v,e[i].w,e[i].id});
            G[e[i].v].push_back((edge){0,e[i].u,e[i].w,e[i].id});
        }
    for(auto &&i:G[1]){
        val[i.v]=i.w,id[i.v]=i.id;
        fa[1]=i.v,dfs(i.v,1);
    }
    for(int i=1;i<=m&&cnt>k;++i)
    {
        if(e[i].u!=1&&!vis[i])
        {
            int u=find(e[i].u),v=find(e[i].v);
            if(u==v)continue;
            if(val[u]!=e[i].w&&val[v]!=e[i].w)continue;
            if(val[v]==e[i].w)swap(u,v);
            fa[u]=v,--cnt;
            print.insert(e[i].id),print.erase(id[u]);
        }
    }
    if(cnt==k){
        pi(n-1,'\n');
        for(auto i:print)pi(i,' ');
    }
    else pi(-1);
    return 0;
}

CF125E MST Company

原文：https://www.cnblogs.com/LLCSBlog/p/11679091.html