/*
poj 1018 Communication System
题意:在n行里,每行里有mi个运输机,从一行选择一个,最后算得选择的运输机min(B)/sum(P),使之最大。
题解: dp[i][j]代表前i行,min(B)为j的最小花费钱。
注意有意义的j个数是变化的。
if(b[i] >= j)
dp[j] = min(dp[j],ans+p[i]);
else
dp[b[i]] = min(dp[b[i]],ans+p[i]);
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
const int N = 1510;
int b[N],p[N];
int dp[N];
int ans[N];
int main()
{
int T;
cin >> T;
while(T--)
{
for(int i = 0; i < N; i++)
dp[i] = INF;
int n,m;
cin >> n >> m;
queue<int> Q;
for(int j = 0; j < m; j++)
{
cin >> b[j] >> p[j];
dp[b[j]] = min(dp[b[j]],p[j]);
ans[b[j]] = dp[b[j]];
Q.push(b[j]);
}
for(int i = 1; i < n; i++)
{
for(int j = 0; j < N; j++)
dp[j] = INF;
cin >> m;
for(int j = 0; j < m; j++)
cin >> b[j] >> p[j];
int len = Q.size();
while(len--)
{
int f = Q.front();
Q.pop();
int flag = 0;
for(int j = 0; j < m; j++)
{
if(b[j] >= f)
{
dp[f] = min(dp[f],ans[f]+p[j]);
flag = 1;
}
else
dp[b[j]] = min(dp[b[j]],ans[f]+p[j]);
}
if(flag)
Q.push(f);
}
for(int j = 0; j < m; j++)
if(dp[b[j]] != INF)
Q.push(b[j]);
for(int j = 0; j < N; j++)
ans[j] = dp[j];
}
double answer = 0;
while(!Q.empty())
{
int x = Q.front();
Q.pop();
double f = x*1.0/ans[x];
answer = max(answer,f);
}
printf("%.3lf\n",answer);
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-200135.html