#P4819. [Sdoi2017]新生舞会

    ID: 3932 传统题 3000ms 128MiB 尝试: 1549 已通过: 602 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案图论带权二分图匹配KM 算法数值计算与优化定点数十进制舍入CF2300杂项分数规划费用流

[Sdoi2017]新生舞会

题目描述

学校举办新生舞会,Cathy 负责给 nn 个男生和 nn 个女生安排舞伴。每人必须恰好有一名异性舞伴。

Cathy 根据同学间是否相识等因素,得到男生 ii 和女生 jj 配对的喜悦程度 ai,ja_{i,j}。她也根据身高、体重等因素,得到两人的不协调程度 bi,jb_{i,j}。她想先据此求出一种方案,再手动微调。

设一种配对方案得到 nn 对舞伴,各对的喜悦程度为 a1′,…,an′a'_1,\ldots,a'_n,不协调程度为 b1′,…,bn′b'_1,\ldots,b'_n。求下式的最大值。

C=∑i=1nai′∑i=1nbi′.C=\frac{\sum_{i=1}^{n}a'_i}{\sum_{i=1}^{n}b'_i}.

输入格式

从标准输入读入数据。第一行一个整数 nn。

接下来 nn 行,每行 nn 个整数,第 ii 行第 jj 个数为 ai,ja_{i,j}。

再接下来 nn 行,每行 nn 个整数,第 ii 行第 jj 个数为 bi,jb_{i,j}。

输出格式

向标准输出写入一行一个数,表示 CC 的最大值,四舍五入保留 66 位小数。输出的数值须与标准输出一致。

样例

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
5.357143

数据范围与约定

  • 对于 10%10\% 的数据,1≤n≤51\le n\le 5。
  • 对于 40%40\% 的数据,1≤n≤181\le n\le 18。
  • 另有 20%20\% 的数据,bi,j=1b_{i,j}=1。
  • 对于 100%100\% 的数据,1≤n≤1001\le n\le 100,1≤ai,j,bi,j≤1041\le a_{i,j},b_{i,j}\le 10^4。