【题意】：给出n个点，m条边，边分为两种，一种是A公司的，一种是B公司的。边上有权值，问用n-1条边把n个点连起来的最小费用是多少，其中A公司的边刚好有k条。题目保证有解。
思路：我们发现，如果我们给白边增加权值，做最小生成树，由于白边权值增大，导致不容易选白边。记f(x)为给白边增加x权值，做最小生成树后，选白边的数量，可以发现，f(x)随x增大而减小。所以可以二分x
首先，直接做MST的话白色边的数量是无法估计的。可能比要求的多，也可能更少
所以考虑怎样调整白色边的数量
通过这个思路，可以想到如果把所有白色边的权值加上/减去一个Δ，那么不考虑答案正确性，可以保证这时候MST跑出来之后白色边的数量一定会增加/减少
那么我们就可以直接二分一个值，使得白边的数量符合要求。
事实上可以证明当我们限定白边的数量一定的时候，MST的答案也是唯一的
那么我们在白边上加上Δ之后算出来MST的答案会多出need*Δ，直接减掉就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int v1,v2;
int w;
} s[],t[];
int n,m,k,cnts,cntt;
int father[],sum;
int cmp(const node a,const node b)
{
return a.w<b.w;
}
int find(int x)
{
int i=x,root;
while(x!=father[x])
x=father[x];
root=x;
x=i;
while(x!=father[x])
{
i=father[x];
father[x]=root;
x=i;
}
return root;
}
int deal(int x)
{
for(int i=; i<=n; i++)
father[i]=i;
int lens=,lent=,pp=;
sum=;
while(lens<cnts||lent<cntt)
{ if(s[lens].w+x<=t[lent].w)
{
int s1=find(s[lens].v1);
int s2=find(s[lens].v2);
if(s1!=s2)
{
father[s1]=s2;
sum+=s[lens].w+x;
pp++;
}
lens++;
}
else
{
int s1=find(t[lent].v1);
int s2=find(t[lent].v2);
if(s1!=s2)
{
father[s1]=s2;
sum+=t[lent].w;
}
lent++;
} }
if(pp>=k) return ;
else return ;
}
int main()
{
int text=;
while(scanf("%d%d%d",&n,&m,&k)>)
{
cnts=,cntt=;
for(int i=; i<m; i++)
{
int v1,v2,w,tmp;
scanf("%d%d%d%d",&v1,&v2,&w,&tmp);
if(tmp==)
{
s[cnts].v1=v1;
s[cnts].v2=v2;
s[cnts].w=w;
cnts++;
}
if(tmp==)
{
t[cntt].v1=v1;
t[cntt].v2=v2;
t[cntt].w=w;
cntt++;
}
}
sort(s,s+cnts,cmp);
sort(t,t+cntt,cmp);
t[cntt].w=s[cnts].w=(<<);
printf("Case %d: ",++text);
int l=-,r=;
int ans=;
while(l<=r)
{
//sum=0;
int mid=(l+r)/;
if(deal(mid))
{
l=mid+;
ans=sum-mid*k;
}
else r=mid-;
}
printf("%d\n",ans);
}
return ;
}