题解 | 旅游

#include <bits/stdc++.h>
typedef long long ll;
const int N = 2e5+10;
using namespace std;
struct Node
{
    int u,v;
    ll w;
}e[N];

bool cmp(Node a,Node b)
{
    return a.w<b.w;
}

ll n,m,c;
int fa[N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}



int main()
{   
    cin>>n>>m>>c;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        ll w;
        cin>>u>>v>>w;
        e[i].u=u;
        e[i].v=v;
        e[i].w=w;
    }

    sort(e+1,e+1+m,cmp);
    vector<int>ed;
    for(int i=1;i<=m;i++)
    {
        int fau = find(e[i].u);
        int fav = find(e[i].v);
        if(fau!=fav)
        {
            fa[fau]=fav;
            ed.push_back(e[i].w);
        }
    }

    sort(ed.begin(),ed.end());
    reverse(ed.begin(),ed.end());
    ll rest = c;
    int cnt = 0;
    int sz = ed.size();
    for(int i=0;i<sz;i++)
    {
        if(rest>=(i+1)*ed[i])
        {
            rest -= (i+1)*ed[i];
            cnt++;
        }
        else break;
    }
    
    if(cnt==sz)cout<<0<<endl;
    else cout<<ed[cnt]<<endl;

    
    

    return 0;
}

思路：利用最小生成树，获取最少所需要的建图成本，接下来利用贪心策略，从最大的建边成本开始减，保证总成本最低