P4086【SDOI2017】新生舞会 | ||
|
问题描述
学校组织了一次新生舞会,Cathy 作为经验丰富的老学姐,负责为同学们安排舞伴。
有 \(n\) 个男生和 \(n\) 个女生参加舞会,一个男生和一个女生一起跳舞,互为舞伴。
Cathy 收集了这些同学之间的关系,比如两个人之前是否认识,计算得出 \(a_{i, j}\),表示第 \(i\) 个男生和第 \(j\) 个女生一起跳舞时他们喜悦程度。
Cathy 还需要考虑两个人一起跳舞是否方便,比如身高体重差别会不会太大,计算得出 \(b_{i, j}\) 表示第 \(i\) 个男生和第 \(j\) 个女生一起跳舞时的不协调程度。
当然,还需要考虑很多其他间题。
Cathy 想先用一个程序通过 \(a_{i, j}\) 和 \(b_{i, j}\) 求出一种方案,再手动对方案进行微调。
Cathy 找到你,希望你帮她写那个程序。
一个方案中有 \(n\) 对舞伴,假设每对舞伴的喜悦程度分别是 \(a'_1, a'_2, \ldots, a'_n\),假设每对舞伴不协调程度分别是 \(b'_1, b'_2, \ldots, b'_n\)。令
Cathy 希望 C 值最大。
输入格式
第一行一个整数 \(n\)。
接下来 \(n\) 行,每行 \(n\) 个正整数,第 \(i\) 行第 \(j\) 个数表示 \(a_{i, j}\)。
接下来 \(n\) 行,每行 \(n\) 个正整数,第 \(i\) 行第 \(j\) 个数表示 \(b_{i, j}\)。
输出格式
一行一个数,表示 \(C\) 的最大值。四舍五入保留六位小数,选手输出的小数需要与标准输出相等。
样例输入
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
样例输出
5.357143
提示
样例输入
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
样例输出
5.357143
对于 \(10\%\) 的数据,\(1 \leq n \leq 5\);
对于 \(40\%\) 的数据,\(1 \leq n \leq 18\);
另外存在 \(20\%\) 的数据,\(b_{i, j} = 1\);
对于 \(100\%\) 的数据,\(1 \leq n \leq 100, 1 \leq a_{i, j} \leq 10 ^ 4,1 \leq b_{i, j} \leq 10 ^ 4\)。