给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
原数据出错，现已更新 by liutian,但未重测---2016.6.24
Input: 3 4 1 0 1 5 0 1 2 6 0 0 1 2 1 1 2 9 1 Output: 8
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m,k,ans,fa[MAXN];
struct Edge{
int u,v,w,colour;
}a[MAXN],b[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
inline bool cmp(const Edge &p,const Edge &q){
if(p.w==q.w)return p.colour<q.colour;
return p.w<q.w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
bool kruskal(int x){
int s=0,num=0;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
b[i]=a[i];
if(a[i].colour==0)b[i].w+=x;
}
sort(b+1,b+m+1,cmp);
ans=0;
for(int i=1;i<=m&&s<n-1;i++)
if(find(b[i].u)!=find(b[i].v)){
uniun(b[i].u,b[i].v);
ans+=b[i].w;
num+=(b[i].colour==0?1:0);
s++;
}
return (num>=k?true:false);
}
void work(){
int l=-100,r=100,mid,s;
while(l<=r){
mid=l+r>>1;
if(kruskal(mid)){s=ans-mid*k;l=mid+1;}
else r=mid-1;
}
printf("%d\n",s);
}
void init(){
n=read();m=read();k=read();
for(int i=1;i<=m;i++){
a[i].u=read();a[i].v=read();a[i].w=read();a[i].colour=read();
a[i].u++;a[i].v++;
}
}
int main(){
init();
work();
return 0;
}
原文：https://www.cnblogs.com/Yangrui-Blog/p/9488655.html