首页 > 代码库 > 【Earthquake, 2001 Open 】 0-1 分数规划

【Earthquake, 2001 Open 】 0-1 分数规划

2024-08-18 08:14:17   254人阅读

71  奶牛施工队
一场地震把约翰家园摧毁了，坚强的约翰决心重建家园。约翰已经修复了 N 个牧场，他需要再
修复一些道路把它们连接起来。碰巧的是，奶牛们最近也成立了一个工程队，专门从事道路修复。而
然，奶牛们很有经济头脑，如果无利可图，它们是不会干的。
约翰和奶牛达成了协议，约翰向奶牛支付 F 元，奶牛负责修路，但不必修复所有道路，只要确保
所有牧场连通即可。可供奶牛选择修复的道路有 M 条，第 i 条道路连接第 Ui 个牧场和第 Vi 个牧场，
修复需要 Ti 分钟，支出成本为 Ci。保证连通所有牧场的道路修复方案总是存在的。奶牛们关注的是
挣钱速度，即总利润和总施工时间的比值。请帮助奶牛们选择修复哪些道路，才能使它们在单位时间
里的利润最大？
输入格式
? 第一行：三个整数 N， M 和 F， 1 ≤ N ≤ 400 , 1 ≤ M ≤ 10000 , 1 ≤ F ≤ 2 × 109
? 第二行到第 M + 1 行：第 i + 1 行有四个整数 Ui， Vi， Ci 和 Ti， 1 ≤ Ui,Vi ≤ N, 1 ≤ Ci,Ti ≤
2 × 109
输出格式
? 单个浮点数：表示施工队的最大挣钱速度，以四舍五入的方法保留四位小数，如果这个项目一
定亏本，输出 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
解释
修最后四条道路，成本总和为 83，时间总和
为 16，所以单位时间的利润为 (100 ? 83)/16 =
1. 0625

 

【分析】

　　因为又是一题0-1分数规划，就再写一下。。

　　其实就是个二分？

　　二分答案mid，即要求[F-sigma(Ci) ]/sigma(Ti)>=mid

　　就是F>=sigma(Ci+mid*Ti)

　　右边尽量小就更有可能成立，就用最小1生成树krustal。

　　嗯

 

技术分享 
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 #define Maxn 410
10 #define Maxm 10010
11 
12 struct node
13 {
14     int x,y,a,b;
15     double c;
16 }t[Maxm*2];
17 
18 int fa[Maxn],n,m;
19 double f;
20 
21 bool cmp(node x,node y) {return x.c<y.c;}
22 
23 int ffa(int x)
24 {
25     if(fa[x]!=x) return ffa(fa[x]);
26     return fa[x];
27 }
28 
29 bool check(double x)
30 {
31     for(int i=1;i<=m;i++) t[i].c=t[i].a+x*t[i].b;
32     sort(t+1,t+1+m,cmp);
33     double sum=0;int cnt=0;
34     for(int i=1;i<=n;i++) fa[i]=i;
35     for(int i=1;i<=m;i++)
36     {
37         if(ffa(t[i].x)!=ffa(t[i].y))
38         {
39             fa[ffa(t[i].x)]=ffa(t[i].y);
40             cnt++;
41             sum+=t[i].c;
42         }
43         if(cnt==n-1) break;
44     }
45     return (cnt==n-1)&&(f>=sum);
46 }
47 
48 void ffind(double l,double r)
49 {
50     while(r-l>0.000001)
51     {
52         double mid=(l+r)/2;
53         if(check(mid)) l=mid;
54         else r=mid;
55     }
56     printf("%.4lf\n",l);
57 }
58 
59 int main()
60 {
61     double sm=0;
62     scanf("%d%d%lf",&n,&m,&f);
63     for(int i=1;i<=m;i++)
64     {
65         scanf("%d%d%d%d",&t[i].x,&t[i].y,&t[i].a,&t[i].b);
66         sm+=t[i].a;
67     }
68     ffind(0,sm);
69     return 0;
70 }
OwO

 

2016-10-31 20:09:07

 

【Earthquake, 2001 Open 】 0-1 分数规划


联系
我们