整体二分\(~~~~~~~~\)个鬼嘞

汗，此整体非彼整体2333

这是一道二分题不假。而是将整体的位置进行二分

偶然时看到这个题。

百思不得其解，然后网上一查。恍然大悟呀

大体就是说（使用克鲁斯卡尔）。如果选了多于need条白边，就将所有白边的边权加上一个数，如果小于need条，就将所有白边的权值减去一个数

然后发现，这是具有单调性的。所以我们二分这个减去或加上的数就可以。

不过为什么不直接贪心的选取need条白边呢？

钟梓俊

貌似网上的题解现在还没有给出具体的证明和数据，那么我就来发一下。

如果我们选了 needneed 条较小的白边，那么可能会影响黑边的选择。下面是一组可以卡掉直接选need条白边的数据，如下。

3 4 10 1 5 01 2 6 00 1 2 11 2 9 1

#include
    
      #include
     
      #include
      
       #include
       
        using std::sort;const int maxn=101000;struct node{    int p1,p2;    int weight;    int c;    bool operator <(const node &a)const     {        if(weight==a.weight)    return c
        
         =N;}int main(){    scanf("%d%d%d",&v,&e,&N);    for(int i=1;i<=e;i++)        scanf("%d%d%d%d",&line[i].p1,&line[i].p2,&line[i].weight,&line[i].c);    int l=-101,r=101,end;    while(l<=r)    {        int mid=(l+r)/2;        if(check(mid))            l=mid+1,end=mid;        else r=mid-1;    }    check(end);    printf("%d\n",ans-N*end);//最后减去}