#P6931. 荒野聚餐

    ID: 6762 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-对偶建模带权二分图匹配KM 算法增广路

荒野聚餐

题目描述

参加聚餐的鸟人有 NN 只雄性和 NN 只雌性。雄性 ii 与雌性 jj 的亲和度为非负整数 ai,ja_{i,j}。你可以为每只鸟人分别支付任意非负实数,支付多少,它就获得多少快乐。

你也可以在音乐设备上花费任意非负实数 SS。如果音乐设备的价格是 CC,每对异性鸟人所需的快乐总和会降低 S/CS/C。也就是说,若雄性 ii 和雌性 jj 的快乐分别为 xi,yjx_i,y_j,则必须满足

xi+yj+SC≥ai,j.x_i+y_j+\frac{S}{C}\ge a_{i,j}.

每个询问独立给出一个价格 CC。求满足所有要求的最小总花费 S+∑ixi+∑jyjS+\sum_i x_i+\sum_j y_j。

输入格式

第一行一个整数 Num\mathrm{Num},表示测试点编号。 第二行两个整数 N,QN,Q,分别表示每类鸟人的数量和询问数。 接下来 NN 行,每行 NN 个整数,第 ii 行第 jj 个数为 ai,ja_{i,j}。 接下来 QQ 行,每行一个整数 CC。

输出格式

每个询问输出一行一个实数,保留一位小数。保证精确答案的小数点后第二位不是 44 或 55。

样例输入 1

1
1 1
5
1

样例输出 1

5.0

样例输入 2

2
3 3
3 0 0
4 5 0
0 4 3
1
2
5

样例输出 2

5.0
8.0
11.0

数据范围与约定

对于所有数据,1≤N≤5001\le N\le500,1≤Q≤50001\le Q\le5000,0≤ai,j≤1090\le a_{i,j}\le10^9,1≤C≤1091\le C\le10^9。

子任务 分值 NN QQ 特殊性质
1 3 =1=1 ≤5\le5 无
2 15 ≤5\le5 ai,j,C≤5a_{i,j},C\le5
3 22 ≤50\le50 =1=1 C=109C=10^9
4 25 ≤50\le50 无
5 12 ≤200\le200 ≤5000\le5000
6 23 ≤500\le500

原 PDF 题面