%%%
by huhao @ 2019-09-10 18:13:00
这是我50分代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while('0'<=c&&c<='9'){
a=a*10+c-48;
c=getchar();
}
return a;
}
#define MN 200005
struct data{
int a,b,c;
bool friend operator<(data a,data b){
return a.c<b.c;
}
}w[2][MN];
int anss,tmp[MN];
int n,m,F,V,Fa[MN],cnt[2];
data Get(int l,int r){
if(l>cnt[0])return w[1][r];
if(r>cnt[1])return w[0][l];
if(w[0][l]<w[1][r]) return w[0][l];
return w[1][r];
}
int Find(int a){
if(Fa[a]==a)return a;
return Fa[a]=Find(Fa[a]);
}
signed main(){
n=read();m=read();
int ned=read();
int a,b,c;
for(int i=1;i<=m;++i){
a=read()+1;b=read()+1;c=read();int x=read()^1;
w[x][++cnt[x]].a=a;w[x][cnt[x]].b=b;w[x][cnt[x]].c=c;
}
sort(w[0]+1,w[0]+1+cnt[0]);
sort(w[1]+1,w[1]+1+cnt[1]);
int l=-105,r=105;
int sum;
while(l+1<r){
int mid=(l+r)>>1;
sum=0;
for(int i=1;i<=cnt[1];++i)
tmp[i]=w[1][i].c,w[1][i].c+=mid;
for(int i=1;i<=n;++i)Fa[i]=i;
int Cnt=0,CNT1=0,L=1,R=1;
while(Cnt<n&&(L<=cnt[0]||R<=cnt[1])){
data x=Get(L,R);
int fa=Find(x.a),fb=Find(x.b);
if(fa!=fb)Fa[fa]=fb,Cnt++,sum+=x.c;
if(x.c==w[1][R].c) {
R++;
if(fa!=fb)CNT1++;
}
else L++;
}
if(CNT1>=ned)
l=mid;
else r=mid;
for(int i=1;i<=cnt[1];++i)w[1][i].c=tmp[i];
}
anss=sum-ned*l;
printf("%d",anss);
return 0;
}
```
这是100分：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while('0'<=c&&c<='9'){
a=a*10+c-48;
c=getchar();
}
return a;
}
#define MN 200005
struct data{
int a,b,c;
bool friend operator<(data a,data b){
return a.c<b.c;
}
}w[2][MN];
int anss,tmp[MN];
int n,m,F,V,Fa[MN],cnt[2];
data Get(int l,int r){
if(l>cnt[0])return w[1][r];
if(r>cnt[1])return w[0][l];
if(w[0][l]<w[1][r]) return w[0][l];
return w[1][r];
}
int Find(int a){
if(Fa[a]==a)return a;
return Fa[a]=Find(Fa[a]);
}
signed main(){
n=read();m=read();
int ned=read();
int a,b,c;
for(int i=1;i<=m;++i){
a=read()+1;b=read()+1;c=read();int x=read()^1;
w[x][++cnt[x]].a=a;w[x][cnt[x]].b=b;w[x][cnt[x]].c=c;
}
sort(w[0]+1,w[0]+1+cnt[0]);
sort(w[1]+1,w[1]+1+cnt[1]);
int l=-105,r=105;
int sum;
while(l+1<r){
int mid=(l+r)>>1;
sum=0;
for(int i=1;i<=cnt[1];++i)
tmp[i]=w[1][i].c,w[1][i].c+=mid;
for(int i=1;i<=n;++i)Fa[i]=i;
int Cnt=0,CNT1=0,L=1,R=1;
while(Cnt<n&&(L<=cnt[0]||R<=cnt[1])){
data x=Get(L,R);
int fa=Find(x.a),fb=Find(x.b);
if(fa!=fb)Fa[fa]=fb,Cnt++,sum+=x.c;
if(x.c==w[1][R].c) {
R++;
if(fa!=fb)CNT1++;
}
else L++;
}
if(CNT1>=ned) {
l=mid;
anss=sum-ned*l;
}
else r=mid;
for(int i=1;i<=cnt[1];++i)w[1][i].c=tmp[i];
}
printf("%d",anss);
return 0;
}
```
它们只有个地方不一样：
`anss=sum-ned*l;`
第一份最后统计，第二份每次都统计
求大佬解释一下，感激不尽
另外小蒟蒻的二分比较奇葩，请注意一下
by skydogli @ 2019-09-10 18:13:22
@[skydogli](/space/show?uid=7480) 因为统计是建立在CNT1>=ned的基础上的
by Kubic @ 2019-09-10 18:15:38
@[Kubic](/space/show?uid=119621) 谢谢巨佬，但应该不是这个问题，我的l只会在这里改变，然后我再交了一次记录l是否改变，显示都是改变的，那么答案也应该没错才对？
by skydogli @ 2019-09-10 18:20:33
@[skydogli](/space/show?uid=7480)
1、我不是巨佬
2、请问您如何通过提交代码知道每次都改变了？
by Kubic @ 2019-09-10 18:23:39
@[Kubic](/space/show?uid=119621) l改变时vis=1,如果vis=0说明从始至终l值为改变
by skydogli @ 2019-09-10 18:27:30
未
by skydogli @ 2019-09-10 18:28:20
@[skydogli](/space/show?uid=7480) 但是如果在外面的话，sum和ned可能已经改变了，就与最后一个满足条件的不同了
by Kubic @ 2019-09-10 18:31:29
@[Kubic](/space/show?uid=119621) 哦！谢谢大佬！！！
by skydogli @ 2019-09-10 18:46:03
Orz
by longlongzhu123 @ 2019-09-10 19:00:30