小白牛客月赛69D题旅游

[链接]https://ac.nowcoder.com/acm/contest/52441/D

题意：有n个城市，m条边（无向图），每条边有一个边权a。第k次操作时消耗为k * a。要求总消耗不能超过c，而且边权小于p的无消耗。求出最小的p使得满足条件。

题解：先运用最小生成树算法Kruskal，将边从小到大排序，找出不在集合中的点，记录添加的边，直到所有点都在集合中，运用了并查集的知识。之后由于第k次操作消耗的为k * a，所以应该从最大的边开始操作，一步步判断是否满足条件，当出现不满足的条件时，返回当前边的大小，因为上面采用的都是最优的策略，所以p最小为不满足条件的边。通俗来说就是c负担不起了，只能让p出手，将下面的边无消耗才能满足条件。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e5+50;
const int mod = 1e9+7;
LL p[N];
LL n,m;
LL c;
LL g[N];
LL dit=0;

struct Edge//边集
{
  int x,y,a;
    bool operator<(const Edge &w)const
    {
        return a<w.a;
    }
}edge[N];

int find(int n)//并查集查找祖宗
{
    if(p[n]!=n)p[n]=find(p[n]);
    return p[n];
}



void solve()
{
    cin>>n>>m>>c;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    
    for(int i=1;i<=n;i++)p[i]=i;
    sort(edge,edge+m);
    
    for(int i=0;i<m;i++)
    {
        int a = edge[i].x; int b = edge[i].y;
        int pa = find(a);int pb = find(b);
        if(pa!=pb)
        {
            p[pa]=pb;
            g[++dit] = edge[i].a;
        }
    }

    LL ope = dit;//从上往下加 金额超过c说明不满足 只能让国家来修
    for(LL i = 1;i<=dit;i++)
    {
        if(c>=i * g[ope])
            c-=i * g[ope--];//这里只能让c来减，因为用一个sum来加的话，会爆long long 的范围，只能减
        else
        {
            cout<<g[ope]<<endl;
            return ;
        }
    }
    cout<<0<<endl;
    
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T = 1;
    while(T--)
    {
        solve();
    }
}