POJ 1018 Communication System

Communication System

Time Limit: 1000MS

Memory Limit: 10000K

Total Submissions: 28182

Accepted: 10049

Description

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices. By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

题目链接:http://poj.org/problem?id=1018

题意:

某公司要建立一套通信系统,该通信系统需要n种设备,而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产,而每个厂家生产的同种设备都会存在两个方面的差别:带宽bandwidths 和 价格prices。

现在每种设备都各需要1个,考虑到性价比问题,要求所挑选出来的n件设备,要使得B/P最大。

其中B为这n件设备的带宽的最小值,P为这n件设备的总价。

分析:此题目可用多种方法求解,DP 、 搜索 、贪心 、三分法 

这里讲dp的思路。

我们定义状态dp 【i】【j】 表示选择了前 i 个宽带其容量为 j 的最小费用。 

很容易得到转移方程 :dp【i】【j】=min(dp【i】【j】,dp【i-1】【k】+p);

注意选择 j 的时候的大小情况。

顺便提供一下贪心的思路。(正确性未知)

从初始的第一个要选的宽带的每一个开始,每次向下贪心选择一个总的 B/P 的最大值,找出其中最大的既为答案。有兴趣的可以验证一下正确性!

dp代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <iomanip>
 5 using namespace std;
 6 
 7 const int maxn=1100;
 8 const int inf=0x3f3f3f3f;
 9 int dp[maxn];
10 
11 struct node{
12     int flow,sum;
13     node(int flow0=0,int sum0=0){
14         flow=flow0,sum=sum0;
15     }
16 };
17 
18 void solve(){
19     queue <node> q;
20     q.push(node(inf,0));
21     int n,m,flow,price;
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++){
24         scanf("%d",&m);
25         for(int i=0;i<maxn;i++) dp[i]=inf;
26         while(m-- >0){
27             scanf("%d%d",&flow,&price);
28             int qsize=q.size();
29             while(qsize-- >0){
30                 node s=q.front();
31                 q.pop();
32                 if(s.flow<flow){
33                     if(s.sum+price<dp[s.flow]) dp[s.flow]=s.sum+price;
34                 }else{
35                     if(s.sum+price<dp[flow]) dp[flow]=s.sum+price;
36                 }
37                 q.push(s);
38             }
39         }
40         while(!q.empty()) q.pop();
41         for(int i=0;i<maxn;i++){
42             if(dp[i]<inf) q.push(node(i,dp[i]));
43         }
44     }
45     double ans=0;
46     while(!q.empty()){
47         node s=q.front();
48         q.pop();
49         if(double(s.flow)/double(s.sum) > ans) ans= double(s.flow)/double(s.sum) ;
50     }
51     cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;
52 }
53 
54 int main(){
55     int t;
56     scanf("%d",&t);
57     while(t-- >0){
58         solve();
59     }
60     return 0;
61 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GIS讲堂

Arcgis for Js之Graphiclayer扩展详解

在前两节,讲到了两种不同方式的聚类,一种是基于距离的,一种是基于区域范围的,两种不同的聚类都是通过扩展esri/layers/GraphicsLayer方法来实...

1733
来自专栏闻道于事

使用ichartjs生成图表

官网:http://www.ichartjs.com/   ichartjs 是一款基于HTML5的图形库。使用纯javascript语言, 利用HTML5的c...

5537
来自专栏数据小魔方

教你如何优雅的用R语言调用有道翻译

最近刚发现了个有趣的包,一个R语言发烧友开发了R语言与有道在线翻译的接口,可能这位大神也是一个受够了每天打开网页狂敲键盘查词的罪,索性自己动手,从此丰衣足食。 ...

2303
来自专栏数据结构与算法

洛谷P2704 [NOI2001]炮兵阵地(状压dp)

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示)...

632
来自专栏AI派

如何使用Python伪造一点也不假的假数据呢

工作中,有时候我们需要伪造一些假数据,如何使用 Python 伪造这些看起来一点也不假的假数据呢?

1613
来自专栏HansBug's Lab

1740: [Usaco2005 mar]Yogurt factory 奶酪工厂

1740: [Usaco2005 mar]Yogurt factory 奶酪工厂 Time Limit: 5 Sec  Memory Limit: 64 MB ...

2585

了解与实现“工作量证明”的源头 Hashcash

让我们来看看 Hashcash 的思路:一封要证明其合法性的电子邮件需要附带一些对字符串的 hash 值来证明其耗费了一定的时间/资源运行了某个算法(Hashc...

42811
来自专栏数据结构与算法

BZOJ3669: [Noi2014]魔法森林(瓶颈生成树 LCT)

为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始...

1213
来自专栏牛客网

58到家java开发面经2018.5.18

1640
来自专栏深度学习之tensorflow实战篇

计算机常用算法对照表整理

常用对照: NLP CRF算法: 中文名称条件随机场算法,外文名称conditional random field algorithm,是一种数学算法,是2...

4675

扫码关注云+社区

领取腾讯云代金券