?
#include?
<
iostream
>
#include?
<
set
>
#include?
<
limits
>
using
?
namespace
?std;
struct
?Node
{
????
int
?broad,?price;
????Node()
{}
????Node(
int
?
&
a,
int
&
b)
????????:broad(a),price(b)
????
{}
}
;
Node?data[
100
][
100
];
int
??length[
100
];
int
?main()
{
????
int
?test;
????scanf(
"
%d
"
,
&
test);
????
while
(?test
--
?)
????
{
????????
int
?n;
????????
set
<
int
>
?br;
????????scanf(
"
%d
"
,
&
n);
????????
for
?(?
int
?i
=
?
0
;?i
<
?n;?
++
i?)
????????
{
????????????
int
?d,x,y;
????????????scanf(
"
%d
"
,
&
d);
????????????length[i]
=
?d;
????????????
for
?(?
int
?j
=
?
0
;?j
<
?d;?
++
j?)
????????????
{
????????????????scanf(
"
%d%d
"
,
&
x,
&
y);
????????????????data[i][j]
=
?Node(x,y);
????????????????br.insert(x);????
//
???Save?all?broad?,?use?set?to?avoid?repeating
????????????}
????????}
????????
set
<
int
>
::iterator?pos;
????????
double
?max
=
?numeric_limits
<
double
>
::min();
????????
for
?(?pos
=
?br.begin?();?pos
!=
?br.end?();?
++
pos?)???
//
???for?every?broad
????????
{
????????????
int
???t
=
?
*
pos;
????????????
int
???total
=
?
0
;
????????????
bool
??isok
=
?
false
;
????????????
for
?(?
int
?i
=
?
0
;?i
<
?n;?
++
i?)???
//
??n?devices
????????????
{
????????????????
int
?M
=
?INT_MAX;
????????????????
for
?(?
int
?j
=
?
0
;?j
<
?length[i];?
++
j?)
????????????????????
if
?(?data[i][j].broad
>=
?t?
&&
?data[i][j].price
<
?M?)
????????????????????????M
=
?data[i][j].price;??????
//
???find??the?min?price
????????????????
if
?(?M
==
?INT_MAX?)
????????????????
{
????????????????????isok
=
?
true
;
????????????????????
break
;
????????????????}
????????????????total
+=
?M;?????
????????????}
????????????
if
?(?isok?)?
continue
;
????????????
if
?(?(
double
)t
/
?(
double
)total
>
?max?)?max
=
?(
double
)t
/
?(
double
)total;???
//
??update
????????}
????????printf(
"
%.3lf\n
"
,?max?);
????}
????
return
?
0
;
}
posted on 2008-10-01 22:06
Darren 閱讀(527)
評論(2) 編輯 收藏 引用 所屬分類:
圖論 、
搜索