最小生成树

思路：给每一条白边加上一个权值，后做最小生成树，由于最小生成树的定义，白边的值越小，则树中白边数越多，具有单调性，所以可以二分。二分这个权值，使得白边的个数恰好为所需个数。

这题的思路看完题解后还是捋的清的，但是自己敲代码的时候按照自己写的却不能A掉这道题，把这错误记录下来。

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;

int n,m,s,ans,cnt;
struct node{
    int u,v,c,w,id;
}a[N];
int w[N];
int f[N];
bool cmp(node a,node b){
    if(a.w==b.w) return a.c<b.c;
    return a.w<b.w;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

bool check(int x){
    ans=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(!a[i].c) a[i].w=w[a[i].id]+x;
    }
    cnt=0;
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].u,v=a[i].v;
        if(find(u)!=find(v)){
            f[find(u)]=find(v);
            cnt+=(a[i].c==0);
            ans+=a[i].w;
        }
    }
    if(cnt>=s) return 1;
    return 0;
}
int qu[N];
signed  main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //freopen("2.in","r",stdin);
    // freopen("3.out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>w[i]>>c;
        x++,y++;
        a[i]={x,y,c,w[i],i};
    }
    int l=-100,r=100;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    check(l);
    cout<<ans-s*l<<'\n';
}

错误代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;

int n,m,s,ans,cnt;
struct node{
    int u,v,c,w,id;
}a[N];
int w[N];
int f[N];
bool cmp(node a,node b){
    if(a.w==b.w) return a.c<b.c;
    return a.w<b.w;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

bool check(int x){
    ans=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(!a[i].c) a[i].w=w[a[i].id]+x;
    }
    cnt=0;
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].u,v=a[i].v;
        if(find(u)!=find(v)){
            f[find(u)]=find(v);
            cnt+=(a[i].c==0);
            ans+=w[a[i].id];
        }
    }
    if(cnt>=s) return 1;
    return 0;
}
int qu[N];
signed  main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //freopen("2.in","r",stdin);
    // freopen("3.out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>w[i]>>c;
        x++,y++;
        a[i]={x,y,c,w[i],i};
    }
    int l=-100,r=100;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    check(l);
    cout<<ans<<'\n';
}

刚开始百思不得其解，为什么只能写 “` ans-s*l “` 的版本，后来仔细想了想，这题的边的大小范围太小，导致会有许多边权相等的边，因为在白边和黑边边权相同的情况下先处理了白边，就使得白边的选择数量可能过多或过少（起冲突），二分出来的 $ l $ 只能是一个恰好大一点的值，不能保证在check里的就是最终答案，总而言之，因为边权的范围太小了所以会有冲突，所以只能写减去的版本。（也许不是很好理解）