题解 | 旅游

显然只需要 MST 上的那 条边，先求一遍 MST 过程中把边拿出来。

然后找 的时候也不用二分，因为 取值一定是那些边的边权，遍历并判断就行了。

关于答案的计算，一开始只会修 次，因为就那些边，随便算算就行了。

Code:

#include<bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;
typedef unsigned long long ull;

constexpr int N=1e5+100,M=1e5+100;

constexpr int MOD=998244353;

int n,m,c;

struct edge{
	int u,v,w;
};edge E[N];

int fa[N];

inline int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
}

vector<edge> vec;

inline void solve(){
	cin>>n>>m>>c;
	iota(fa+1,fa+n+1,1);
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		E[i]=(edge){u,v,w};
	}
	sort(E+1,E+m+1,[&](edge x,edge y){
		return x.w<y.w;
	});
	ll ans=0,cnt=n-1;
	for(int i=1;i<=m;i++){
		int xx=find(E[i].u),yy=find(E[i].v);
		if(xx!=yy){
			fa[xx]=yy;
			ans+=(E[i].w*cnt);
			cnt--;w
			vec.push_back(E[i]);
		}
	}
	if(ans<=c){
		cout<<0<<'\n';
		return ;
	}
	ll p=0,cnt2=n-1;
	for(auto _:vec){
		p=_.w;
		if((ans-(_.w*cnt2))>c){
			ans-=(_.w*cnt2);
			cnt2--;
		}
		else{
			break;
		}
	}
	cout<<p<<'\n';
}

signed main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	ios::sync_with_stdio(NULL);
	cin.tie(NULL),cout.tie(NULL);
	int T=1;
//	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}