[백준] 2126 - 지진 (c++)

https://www.acmicpc.net/problem/2126

Olympiad > USA Computing Olympiad > 2000-2001 Season > USACO US Open 2001 Contest > Green 2번

 

문제 요약

N개의 정점과 M개의 양방향 간선으로 이루어진 그래프가 주어진다. 지진이 일어나 모든 간선들이 끊어진 상태이고 모든 정점이 이어질 수 있도록 간선 몇개를 복원해야 한다.

각 간선을 복원 하는데에 시간 t와 비용 c가 든다. 예산은 F이다. 간선을 복원하며 시간당 얻게 되는 이득의 최댓값을 구해라.

 

풀이 (MlogMlogK)

• 매개 변수 탐색
• MST

시간 당 얻는 이득은 (F-∑C)/ ∑T 이다. 결정 문제로 바꾸면 (F-∑C)/ ∑T>=X. 이 식을 이분탐색에 쓸 수 있게 좀 정리해보자. F-∑C>=X*∑T → F-∑C>=X*∑T → F>= ∑(C+X*T) 이렇게 정리하면 C+X*T를 가중치로 두고 크루스칼로 ∑(C+X*T)의 최소를 구할 수 있게 된다. 이를 두고 이분탐색까지 할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct Djs {
    vector<int> p;
    Djs(int size) {
        p.resize(size);
    }
    int find(int a) {
        if (!p[a])
            return a;
        return p[a] = find(p[a]);
    }
    void Union(int a, int b) {
        p[find(a)] = find(b);
    };
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    double n,m,f;cin>>n>>m>>f;
    vector<array<double,4>> ed(m);
    for(auto&[u,v,c,t]:ed) cin>>u>>v>>c>>t;
    double st=0,en=2e9;
    for(int i=0;i<200;i++) {
        double mid =(st+en)/2;
        sort(ed.begin(),ed.end(),[&](array<double,4> a,array<double,4> b) {
            if(mid*a[3]+a[2]<mid*b[3]+b[2])
                return 1;
            return 0;
        });
        Djs djs = Djs(n+1);
        double s =0;
        for(auto&[u,v,c,t]:ed) {
            if(djs.find(u)!=djs.find(v))
                djs.Union(u,v),s+=mid*t+c;
        }
        if(s<=f)
            st=mid;
        else
            en=mid;
    }

    cout<<fixed<<setprecision(4)<< en;
}