}
printf("%.3lf\n",ans);
}
return 0;
}
#include
#include
#include
using namespace std;
#define N 101
struct NODE
{
int b;//宽带
int p;//价格
int id;//设备编号
};
//按带宽、价格、编号依次比较排序
int cmp(const void* a, const void* b)
{
NODE* x =(NODE*)a;
NODE* y =(NODE*)b;
if((x->b)==(y->b))
{
if((x->p)==(y->p))
return (x->id) -(y->id);
else
return (x->p) - (y->p);
}
return (x->b) -(y->b);
}
double max(double a, double b)
{
return a > b a:b;
}
int MaxB[N]; //各种设备对应的带宽最大值
NODE dev[N*N]; //记录所有厂家生产的产品信息
bool vist[N];
int pd; //dev[]指针
int main()
{
int test, i, j;
//freopen("in.txt","r",stdin);
scanf("%d",&test);
while(test--)
{
int n;//设备数
int m = 0; //生产商总数
pd = 0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
int mi;
scanf("%d",&mi);
m +=mi;
MaxB[i] =-1;
for(j=1;j<=mi;j++)
{
pd++;
scanf("%d%d",&dev[pd].b,&dev[pd].p);
dev[pd].id=i;
MaxB[i] = max(MaxB[i], dev[pd].b);
}
}
qsort(dev,m+1,sizeof(NODE),cmp);
bool flag = false;
double ans = 0; // B/P的最大值
for(i=1;i<=m-(n-1);i++) //枚举所有设备带宽的最小带宽B
{ //m-(n-1)是剪枝，因为当设备数>生产商时就不必枚举了
memset(vist,false,sizeof(bool)*(n+1));
vist[dev[i].id] = true;
double price = dev[i].p; //设备总价
int count = 1; //计数器，记录已经选取的设备个数
for(j=i+1;j<=m;j++)
{
if(vist[ dev[j].id])
continue;
if(dev[i].b > MaxB[dev[j].id]) //剪枝
{
flag= true; //当前枚举的“所有设备带宽的最小带宽Bi”比“设备j的最大带宽MaxBj”要大
//说明当前Bi已经越界，无需继续往后枚举
break;
}
vist[dev[j].id] =true;
price +=dev[j].p;
count++;
}
if(flag || count
ans = max(ans, (dev[i].b/price));
}
printf("%.3lf\n",ans);
}
return 0;
}