PKU 1018-Communication System

PKU

1018 Communication System - PKU Wiki*

解法

最小値を仮定するとO(N^2)で最大のM/Pを求めることが出来るので，全ての最小値についてそれを実行する．
O(N^4)ぐらいになる．

実装(C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int vals[10001];
int cnt;
int t,n;
int m[101];
int b[101][101],p[101][101];

int solve(int k,int Min){
	if(k==n){
		return 0;
	}
	int M=99999999;
	for(int i=0;i<m[k];i++){
		if(b[k][i]>=vals[Min]){
			M=min(M,p[k][i]);
		}
	}
	return solve(k+1,Min)+M;
}
int main() {
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		cnt=0;
		for(int i=0;i<n;i++){
			scanf("%d",&m[i]);
			for(int j=0;j<m[i];j++){
				scanf("%d%d",&b[i][j],&p[i][j]);
				vals[cnt++]=b[i][j];
			}
		}
		std::sort(vals,vals+cnt);
		cnt=std::unique(vals,vals+cnt)-vals;
		double res=0.0;
		for(int i=0;i<cnt;i++){
			res=max(res,(double)vals[i]/solve(0,i));
		}
		printf("%.3f\n",res);
	}
	return 0;
}