BZOJ-2654: tree

Description

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。

神题！
发现假如将所有百变加上同一个权值，所选need条白边是不变的。但是选的白边的数量会改变。那么我们二分这个权值，如果选的边数< need则减小权值，反之增大权值。（不过显然可能没有正好need条啊。。。也不知道怎么处理。）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,need,ans;
int fa[51000];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct node
{
    int x,y,w,col;
}a[101000];
bool cmp(node x,node y){return x.w<y.w;}
int check(int x)
{
    for(int i=1;i<=m;++i) if(!a[i].col) a[i].w+=x;
    for(int i=1;i<=n;++i) fa[i]=i;
    sort(a+1,a+m+1,cmp); int dx,dy,re=0;
    for(int i=1;i<=m;++i)
    {
        dx=find(a[i].x); dy=find(a[i].y);
        if(dx!=dy)
        {
            fa[dy]=dx;
            re+=!a[i].col;
        }
    }
    for(int i=1;i<=m;++i) if(!a[i].col) a[i].w-=x;
    return re;
}
int main()
{
    scanf("%d%d%d",&n,&m,&need);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].w,&a[i].col);
        a[i].x++; a[i].y++;
    }
    int l=-101,r=101,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)<=need) r=mid;
        else l=mid+1;
    }
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i) if(!a[i].col) a[i].w+=r;
    sort(a+1,a+m+1,cmp); int x,y,cnt=need;
    for(int i=1;i<=m;++i) if(a[i].col||cnt)
    {
        x=find(a[i].x); y=find(a[i].y);
        if(x!=y)
        {
            cnt-=!a[i].col;
            fa[y]=x;
            ans+=a[i].w;
        }
    }
    ans-=r*need;
    printf("%d",ans);
    return 0;
}