题解 | #旅游#

本题是一道最小生成树的kruskal算法的题目

先用kruskal算法去记录最小生成树的最短边

然后根据题意所给出的要求去进行迭代更新sum，直至找到一个sum值大于牛牛所投入的资金c，输出最后令 sum>=c的损害值

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;

const int N=1e5+10;
int p[N];
vector<int> u;
int n,m,c;
int cnt;

struct node{
    int a;int b;int w;
}edge[N];

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

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

void kruskal()
{
    for(int i=0;i<m;i++)
    {
        int pa=find(edge[i].a);
        int pb=find(edge[i].b);
        int w=edge[i].w;
        
        if(pa!=pb)
        {
            p[pa]=pb;
            cnt++;
            u.push_back(w);
        }
    }
}

signed main()
{
    cin>>n>>m>>c;
    
    
    for(int i=0;i<n;i++) p[i]=i;
    
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edge[i]={a,b,w};
    }
    
    sort(edge,edge+m,cmp);
    
    kruskal();
    
    int k=1;
    int sum=0;
    for(int i=u.size()-1;i>=0;i--)//此处开始对sum进行迭代操作，找出大于c的sum的临界条件
    {
        sum+=u[i]*(k++);
        if(sum>c) {
            printf("%lld",u[i]);
            return 0;
        }
    }
    printf("0");
}