40pts不知道问题何在。

因为已经调了1d了

所以悬赏关注x1

感谢各位大佬于百忙中抽出时间看我的问题代码

#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){
	x=finda(x);
	y=finda(y);
	if(x==y){
		return 1; 
	}
	else{
		return 0;
	}
}
int gb;
int gx;
void check(int cc){
	gx=0;
	gb=0;
	for(int i=0;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		if(line[i].col==0){
            //cout<<"ptest:"<<line[i].c<<endl;
			line[i].c-=cc;//相对顺序会改变 
            //cout<<"ltest:"<<line[i].c<<endl;
		}
	}
	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;
			if(line[i].col==0){
				gx++;
			}
		}
	}
	//跑一次最小生成树 
	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=-1e13;
	int r=1e13;
	for(int i=1;i<=200;i++){
		int mid=1.0*(l+r)/2;
		check(mid);
		if(gx<need){
			l=mid+1;
			
		}
		else{
			r=mid;
		}
	}
	int pron=(r);
	check(pron);
//	cout<<"TEST"<<r<<endl;
	cout<<(int)(pron*gx+gb);
}