← 返回题目列表

Codeforces · 839/E

E. 龙之母

中文机器翻译题面 查看原题

兰尼斯特王国有 n 座城堡,有城墙连接两座城堡,没有两座城堡由多于一堵墙连接,没有城墙将城堡与其自身连接。

詹姆·兰尼斯特爵士发现丹妮莉丝·坦格利安即将攻击他的王国。因此他要保卫自己的王国。他有 k 升一种奇怪的液体。他想在城堡之间分配该液体,因此每个城堡可能包含一些液体(可能为零或非整数升)。之后墙的稳定性定义如下:如果墙连接两个城堡a和b,并且它们分别含有x和y升该液体,则该墙的强度为x·y。

你的任务是打印詹姆·兰尼斯特爵士可以达到的最大可能的墙壁稳定性总和。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 40, 1 ≤ k ≤ 1000)。

接下来是 n 行。这些行的第 i 行包含 n 个整数 ai, 1, ai, 2, ..., ai, n ($$a_{i,j} \in \{0,1\}$$)。如果城堡 i 和 j 有墙连接,则 ai, j = 1。否则等于 0。

对于所有 1 ≤ i、j ≤ n,保证 ai, j = aj, i 且 ai, i = 0。

输出

打印詹姆·兰尼斯特爵士能够达到的最大可能的城墙稳定性总和。

如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

3 1
0 1 0
1 0 0
0 0 0

输出 #1

0.250000000000

输入 #2

4 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

输出 #2

4.000000000000

注意

在第一个样本中,我们可以分别为城堡 1、2、3 分配 0.5、0.5、0 升液体,以获得最大总和 (0.25)。

在第二个示例中,我们可以分别为城堡 1、2、3、4 分配 1.0、1.0、1.0、1.0 升液体,以获得最大总和 (4.0)