【最小生成树+贪心】旅游

比眉伴天荒 2024-03-24 09:15 9阅读 0赞

[D-旅游\_牛客小白月赛69 (nowcoder.com)][D-_69 _nowcoder.com]

题意：

![4e4b3c66132f4a8eb69d2a3c31a62dd0.png][]

思路：

一眼二分了

直接去二分p值，然后对于每个二分的p值，都去做一次最小生成树，<p的让国家出钱，>=p的只能自己出

但是考虑到贡献，肯定自己肯定是先修大的再修小的

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    struct ty{
        int u,v,w;
    }e[mxe<<2];
    bool cmp(ty x,ty y){
        return x.w<y.w;
    }
    vector<ty> E;
    int n,m,c,u,v,w,ans,res=0,cnt=0,cnt1=0;
    int f[mxn];
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    void kruskal(int pr){
        sort(e+1,e+1+m,cmp);
        E.clear();
        for(int i=1;i<=m;i++){
            if(find(e[i].u)==find(e[i].v)) continue;
            join(e[i].u,e[i].v);
            if(e[i].w>pr) E.push_back(e[i]);
        }
    }
    bool check(int mid){
        for(int i=1;i<=n;i++) f[i]=i;
        kruskal(mid);
        res=0;
        for(int i=E.size()-1,k=1;i>=0;i--,k++){
            res+=1ll*k*E[i].w;
        }
        return res<=c;
    }
    void solve(){
        cin>>n>>m>>c;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            e[i]={u,v,w};
        }
        int l=0,r=1e9;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D-_69 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/52441/D
[4e4b3c66132f4a8eb69d2a3c31a62dd0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/557fc65fdc1445fb87086c7ffcfaf3b5.png