地震(quake)

时间：2021-08-28 08:11:48
地震
题目描述

一场地震毁了 Farmer John 的整个农场。他是个有恒心的人,决定重建农场。在重建了所有 n(1<=n<=400)块田野后,他意识到还得修路将它们连起来。完工后,任两个田野间必须有路。研究了地形后, FJ 认为 m(1<=m<=10000)条双向的道路可能建造。由于资金短缺,他希望已尽可能省钱的方式完成整个工程。幸运的是,奶牛们已经成立了针对地震后修建农场道路的工程顾问公司。奶牛们也很有经济头脑,对没有漂亮利润的工作从不感兴趣。奶牛们关心可能的利益。他们已经说定了为修路所获的酬金f(1<=f<=2,000,000,000),并得到一张关于可能的道路、修建每条路的时 间 ( 以 小 时 计 ) ( 1 <=t<=2,000,000,000 ) 以 及 花 费(1<=c<=2000,000,000)的列表。在两块田野间可能有多于一条的道路被列出,所给数据总有可以连通所有田野的修路方案,虽然可能无利可图。

确定奶牛修路最高的盈利率。

输入

♦第一行三个整数 N, M, F。
♦2...M+1 行: 每行四个空格隔开的整数: i, j, c,t 描述两块田夜间的一
条道路。

输出

只包含一个数,保留四位小数,奶牛每个小时可以得到的最大利润,
如果利润非正,输出 0.0000 。

样例输入

5 5 100
1 2 20 5
1 3 20 5
1 4 20 5
1 5 20 5
2 3 23 1

样例输出

1.0625

思路

这道题是二分,即01分数规划(学习笔记)

我们知道修路的价值和代价,我们现在要求每个小时的最高利润

那么问题用数学语言来表达就成了

(借用XZZ博客)

地震(quake)

然后我们再变化一下,就变成了求ci+ti*x最小值;

我们把每条边的权值变成这个,然后跑最小生成树,得到最小值,如果f(x)的值大于0,则证明该x是合法的,如果小于0则不合法..

代码

我觉得我可以去si了,改了好久好久都不知道错哪里

#include<cstdio>

#include<algorithm>

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

#define db long double

typedef long long ll;

il int gi(){

    rg int x=;bool flg=;rg char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')flg=;ch=getchar();}

    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

    return flg?-x:x;

}

const int maxn=,maxm=;

int n,m,f;

struct edge{int a,b,w,t;db v;}e[maxm];

bool operator < (edge a,edge b){return a.v<b.v;}

int fa[maxn];

il int hd(int i){return fa[i]==i?i:hd(fa[i]);}

il bool check(ll mid){

    rep(i,,m)e[i].v=mid/3e6*e[i].t+e[i].w;

    int x=;

    sort(e+,e+m+);rep(i,,n)fa[i]=i;

    db k=f+1e-;

    rep(i,,n){

        while(x<=m&&hd(e[x].a)==hd(e[x].b))++x;

        fa[hd(e[x].a)]=hd(e[x].b),k-=e[x].v;

        if(k<)return ;

    }return ;

}

int main()

{

    n=gi(),m=gi(),f=gi();

    rep(i,,m)e[i].a=gi(),e[i].b=gi(),e[i].w=gi(),e[i].t=gi();

    if(!check(0ll)){puts("0.0000");return ;}

    ll mid,l=,r=2e15;

    while(l<r){

        mid=(l+r)>>;

        if(check(mid+))l=mid+;

        else r=mid;

    }printf("%.4Lf\n",l/(db)3e6);

    return ;

}

相关文章