给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
题解: orz这个二分 首先我们来分析一下 边数与权值的关系 显然的随着白色边的权值增加会导致白色边的数量减少那么 我们可以通过二分找到恰好为need的白边的位置 同同构造MST保证此时的边权和最小 出现的问题是你二分加的权值会出现白边和黑边相等情况 此时优先白边加入 排序的时候加一下限制即可
#include <bits/stdc++.h>
const int MAXN=5e4+10;
using namespace std;
int n,m,ned;
typedef struct node{
int id,u,v,vul,key;
}node;
node d[MAXN<<1];
bool cmp(node aa,node bb){
if(aa.key==bb.key)return aa.id<bb.id;
return aa.key<bb.key;
}
int f[MAXN],key;
int find1(int x){
if(f[x]==x)return x;
else return f[x]=find1(f[x]);
}
bool check(int t){
for(int i=1;i<=m;i++){
if(d[i].id==0)d[i].key=d[i].vul+t;
else d[i].key=d[i].vul;
}
sort(d+1,d+m+1,cmp);key=0;
int cnt=0;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
int t1=find1(d[i].u);int t2=find1(d[i].v);
if(t1==t2)continue;
f[t1]=t2;key+=d[i].key;
if(!d[i].id)cnt++;
}
if(cnt>=ned)return 1;
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&ned);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d%d%d%d",&d[i].u,&d[i].v,&d[i].vul,&d[i].id),d[i].u++,d[i].v++;
int l=-110,r=110,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))l=mid+1,ans=key-ned*mid;
else r=mid-1;
}
printf("%d\n",ans);
}
原数据出错，现已更新 by liutian,但未重测---2016.6.24
原文：https://www.cnblogs.com/wang9897/p/9461808.html