LGP4951 [USACO01OPEN]Earthquake（最优比率生成树）

题意：

一场地震把约翰家的牧场摧毁了， 坚强的约翰决心重建家园。 约翰已经重建了 \(n\) 个牧场，现在他希望能修建一些道路把它们连接起来。研究地形之后，约翰发现可供修建的道路有 \(m\) 条。碰巧的是，奶牛们最近也成立一个工程队，专门从事修复道路。而然，奶牛们很有经济头脑，如果无利可图，它们是不会干的。

奶牛们关注的是挣钱速度，即总利润和总施工时间的比值。约翰和奶牛达成了协议，奶牛负责修建道路，将所有牧场连通，而约翰需要支付 \(f\) 元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的，不过也有可能一些道路的建造成本之和会超过 \(f\)。

请帮助奶牛们选择修复哪些道路，才能使单位时间的利润最大？

\(1≤n≤400\)，\(1 \leq m \leq 10000\)，\(1 \leq f \leq 2 \times 10^9\)

思路：

01分数规划入门题

根据题意列出方程：

\(\frac{f-\Sigma{c_i}}{\Sigma{t_i}}=ans\)

则假设最大答案就是\(ans\)

则有

\(f-\Sigma{c_i}-ans*\Sigma{t_i}=0\)

发现只有在最大答案的时候才会满足上式等于\(0\)。

考虑二分答案

若\(Mid \leq ans\),则有 \(f-\Sigma{c_i}-Mid*\Sigma{t_i}>=0\)
若\(Mid > ans\),则有 \(f-\Sigma{c_i}-Mid*\Sigma{t_i}<0\)

不难发现，函数\(F(x)=f-\Sigma{c_i}-x*\Sigma{t_i}\)，是一个从左上到右下，经过原点逐渐递减的函数。

所以正好满足二分的性质,根据函数来进行二分即可求得\(ans\)。

假设\(F(x)>0\)，此时\(x\)一定小于最大答案\(ans\)，于是向右继续查找。
假设\(F(x)<0\)，此时\(x\)一定大于最大答案\(ans\)，与假设矛盾，不可能存在，于是向左继续查找。

将函数化简成\(F(x)=f-\Sigma{(c_i+x*t_i)}\)，接下来在二分时将每条边的边权转换为\(c_i+x*t_i\)，求一个最小生成树。

至于为什么求最小生成树，可以理解为找到一组最小的\(\Sigma{(c_i+x*t_i)}\)，使得\(F(x)\)尽可能的大于等于\(0\)，遍历到尽可能多的大于等于\(0\)值。

Code:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" :"<<x<<endl
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define eps 1e-6
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
ll powmod(ll a,ll b,ll mod1) {ll res=1;a%=mod1; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod1;a=a*a%mod1;}return res;}
const int maxn=2e5+10;
const int MAXN=2e5+10;
int q[maxn];
ll n,m;
ll a[maxn];
ll b[maxn];
ll dp[maxn];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}

/*
*/

double f;
ll vis[maxn];
double dis[maxn];
int fa[maxn];
ll ln[maxn],rn[maxn];
double c[maxn],ti[maxn];
int get(int x){
    if(x!=fa[x]){
        fa[x]=get(fa[x]);
    }
    return fa[x];
}
struct node
{
    int x,y;
    double val;
    //node(int X,int Y,double vv):x(X),y(Y),val(vv){}
}op[maxn];

bool cmp(node a,node b){
    return a.val<b.val;
}
int check(double ans){
    for(int i=1;i<=n;++i){
        fa[i]=i;
    }
    int cnt=0;
    for(int i=1;i<=m;++i){
        op[++cnt].x=ln[i];
        op[cnt].y=rn[i];
        op[cnt].val=c[i]+ans*ti[i];
    }
    int con=0;
    double sum=0;
    sort(op+1,op+1+cnt,cmp);
    for(int i=1;i<=cnt;++i){
        int fx=get(op[i].x);
        int fy=get(op[i].y);
        if(fx==fy)continue;
        fa[fy]=fx;
        sum+=op[i].val;
        con++;
        if(con==n-1)break;
    }
    if(double(f-sum)>=0.0){
        return 1;
    }
    else return 0;
}
int main(){
    int t;
    srand(time(NULL));
    //scanf("%d",&t);
    t=1;
    while(t--){
        scanf("%lld%lld%lf",&n,&m,&f);
        rep(i,1,m){
            ll l,r;
            scanf("%lld%lld%lf%lf",&ln[i],&rn[i],&c[i],&ti[i]);
        }
        double l=0.0;
        double r=1e12,ans;
        while(l+eps<r){
            double mid=(l+r)/2.0;
            if(check(mid)){
                ans=mid;
                l=mid;
            }
            else{
                r=mid;
            }
        }
        printf("%.4f",ans);
    }
        
    return 0;
}

LGP4951 [USACO01OPEN]Earthquake（最优比率生成树）

原文：https://www.cnblogs.com/quuns/p/14399337.html