旅游（最小生成树&二分）---牛客小白月赛69-D

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f
const int N=4e4+5;
int n,m,c;
int p[N];

struct node{
	int x,y,w;
	bool operator<(const node& t)const{
		return w<t.w;
	}
};
vector<node>e,res;

int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}

bool check(int mid){
	int k=1,sum=0;
	for(int i=0;i<res.size();i++){
		if(res[i].w<=mid) continue;
		sum+=res[i].w*k++;
		if(sum>c) return false;
	}
	return sum<=c;
}

void solve(){
	cin>>n>>m>>c;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		e.push_back({x,y,w});
	}
	sort(e.begin(),e.end());
	
	for(int i=1;i<=n;i++) p[i]=i;
	for(auto it:e){
		int x=it.x,y=it.y;
		x=find(x),y=find(y);
		if(x!=y){
			p[x]=y;	
			res.push_back(it);
		}
	}
	reverse(res.begin(),res.end());
	
	int l=0,r=1e18;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt=1;
//	cin>>tt;
	while(tt--) solve();
	return 0;
}