```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
/*
不考虑need，就是最小生成树
本题是一个下凸函数
*/
struct node{
int s;
int t;
int c;
int col;
}line[100005];
bool cmp(node x,node y){
if(x.c!=y.c)return x.c<y.c;
else return x.col<y.col;
}
int fa[100005];
int n,m,need;
int finda(int x){
if(fa[x]==x) return x;
else{
fa[x]=finda(fa[x]);
return fa[x];
}
}
void unite(int x,int y){
x=finda(x);
y=finda(y);
if(x==y) return;
else fa[x]=y;
}
bool judge(int x,int y){
return finda(x)==finda(y);
}
int gb,gx,cnt;
void check(int cc){
gx=gb=cnt=0;
for(int i=0;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)if(line[i].col==0)line[i].c+=cc;
sort(line+1,line+1+m,cmp);
for(int i=1;i<=m;i++){
if(judge(line[i].s,line[i].t)==1)continue;
else{
unite(line[i].s,line[i].t);
gb+=line[i].c,cnt++;
if(line[i].col==0)gx++;
}
if(cnt==n-1)break;
}
//跑一次最小生成树
for(int i=1;i<=m;i++){
if(line[i].col==0)
line[i].c-=cc;
}
}
signed main(){
ios::sync_with_stdio(false);
cin >> n >> m >> need;
for(int i=1;i<=m;i++){
cin >> line[i].s >> line[i].t >> line[i].c >> line[i].col;
}
int l=-101;
int r=101;
while(l<r){
int mid=(l+r+1)/2;
check(mid);
if(gx<=need)r=mid-1;
else l=mid;
}
check(l);
cout<<(int)(gb-l*need);
}
```
- 上下界太大了
- 要用右偏二分
- 码风....
by _Regenbogen_ @ 2023-09-11 11:25:57
@[h8866](/user/791638) 感谢大佬，马上关注！
by LingHusama @ 2023-09-11 11:28:02
- 整数二分存在取不到need的情况，需要在计算时用黑边替换，也就是说只用 pron*need 不用 pron*gx
@Lingusama
by _Regenbogen_ @ 2023-09-11 11:28:23
我乘号呢？？
by _Regenbogen_ @ 2023-09-11 11:29:06
@[h8866](/user/791638) 敢问大佬为什么存在取不到的情况？不是k+1的情况下f(k)我要增加的话最少+1，按理来说，斜率可以用整数二分出来吧...（蒟蒻不懂）
by LingHusama @ 2023-09-11 11:30:52
@[h8866](/user/791638) 还有，萌新不懂就问，乘号是什么意思啊？
by LingHusama @ 2023-09-11 11:35:20
- 凸性是两端单调
- wqs二分要小数二分才能得到准确的值
你可以自己造一组数据试试
by _Regenbogen_ @ 2023-09-11 11:46:59
乘号是被 Markdown 坑了
by _Regenbogen_ @ 2023-09-11 11:47:32
@[h8866](/user/791638) 射射大佬
by LingHusama @ 2023-09-11 11:49:45