| Codeforces Round 428 (Div. 2) |
|---|
| Закончено |
В Королевстве Ланнистеров 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 (
). Если замки i и j соединены стеной, ai, j = 1. В противном случае оно равно 0.
Гарантируется, что ai, j = aj, i и ai, i = 0 для всех 1 ≤ i, j ≤ n.
Выведите одно число — максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь.
Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 6.
А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если 
.
3 1
0 1 0
1 0 0
0 0 0
0.250000000000
4 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
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.
