题目描述

Description

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

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

题目分析

肯定不能直接做对吧
观察 假设我们把所有的白边加上一个值 那么最小生成树里的白边数量一定变小 反之变大
所以二分我们要加上的哪个值即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
struct your
{   
    int x,y,c,col;
}a[100100];
int sum,num,cnt,f[100010],l=-100,r=1000,mid;
int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
int cmp(your j,your k) { return j.c+(j.col^1)*mid<k.c+(k.col^1)*mid; }
int check()
{
    sum=0,num=0,cnt=0;
    for(int i=1;i<=n;i++) f[i]=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int dx=find(a[i].x),dy=find(a[i].y);
        if(dx==dy) continue;
        num+=(a[i].col^1),sum+=a[i].c,f[dx]=dy,cnt++;
        if(cnt==n-1) break;
    }
    return num;
}
int main()
{   
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].c,&a[i].col),a[i].x++,a[i].y++;
    int ans=0;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check()>=k) ans=sum,l=mid+1;
        else r=mid;
    }
    printf("%d",ans);
    return 0;
}