题解 | 旅游

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e4+10,M=2e4+10;
int n,m,c;
int f[N];
struct Way{
	int dis;
	int a;
	int b;
	bool operator<(const Way& d) const
	{
		return dis<d.dis;
	}
};
vector<Way> edges;

void init()
{
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
}

int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}

void merge(int x,int y)
{
	f[find(x)]=find(y);
}

bool solve(int p)
{
	init();
	vector<int> hei;
	int sum=0;
	int cnt=0;
	for(auto edge:edges)
	{
		if(cnt>=n-1) break;
		if(find(edge.a)!=find(edge.b))
		{
			merge(edge.a,edge.b);
			cnt++;
			if(edge.dis>p)
			{
				hei.push_back(edge.dis);
			}
		}
		
	}
	if(cnt<n-1) return false;
	sort(hei.begin(),hei.end());
	int j=1;
	for(int i=hei.size()-1;i>=0;i--)
	{
		sum+=j*hei[i];
		j++;
	}
	return sum<=c;
}

signed main()
{
	cin>>n>>m>>c;
	while(m--)
	{
		int x,y,a;
		cin>>x>>y>>a;
		edges.push_back({a,x,y});
	}
	sort(edges.begin(),edges.end());
	
	int l=0,r=0x3f3f3f3f;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(solve(mid))
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	return 0;
}