最小生成树+点乘原理

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,c,p;
int fa[2000010];
struct node{
    int st;
    int to;
    int cost;
    bool operator < (const node&a) const{
        return cost < a.cost;
    }
}edge[2000010];
int find(int x){
    if(fa[x]==x) return x;
    else{
        fa[x] = find(fa[x]);
        return fa[x];
    }
}
void merge(int x,int y){
    fa[find(x)] = find(y);
    return;
}
bool check(int number){
    for(int i = 1;i<=n;i++) fa[i] = i;
    int sum = 0;
    int ans[1000000];
    int cnt = 0;
    for(int i = 1;i<=m;i++){
        if(edge[i].cost<=number){
            merge(edge[i].st,edge[i].to);
            continue;
        }
        if(find(edge[i].st)!=find(edge[i].to)){
            merge(edge[i].st,edge[i].to);
            ans[++cnt] = edge[i].cost;
        }
    }
    sort(ans+1,ans+1+cnt);
    int op = 1;
    for(int i = cnt;i>=1;i--){
        sum += ans[i]*op;
        op++;
    }
    if(sum<=c) return true;
    else return false;
}
signed main(){
    cin>>n>>m>>c;
    int x,y,z;
    for(int i = 1;i<=m;i++){
        cin>>edge[i].st>>edge[i].to>>edge[i].cost;
    }
    sort(edge+1,edge+1+m);
    int l = 0;
    int r = 1e18;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)) p = mid,r = mid-1;
        else l = mid+1;
    }
    cout<<p<<endl;
}