English · Original
Chinese · Translation
Formal · Original
There are _n_ castles in the Lannister's Kingdom and some walls connect two castles, no two castles are connected by more than one wall, no wall connects a castle to itself.
Sir Jaime Lannister has discovered that Daenerys Targaryen is going to attack his kingdom soon. Therefore he wants to defend his kingdom. He has _k_ liters of a strange liquid. He wants to distribute that liquid among the castles, so each castle may contain some liquid (possibly zero or non-integer number of liters). After that the stability of a wall is defined as follows: if the wall connects two castles _a_ and _b_, and they contain _x_ and _y_ liters of that liquid, respectively, then the strength of that wall is _x_·_y_.
Your task is to print the maximum possible sum of stabilities of the walls that Sir Jaime Lannister can achieve.
## Input
The first line of the input contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 40, 1 ≤ _k_ ≤ 1000).
Then _n_ lines follows. The _i_\-th of these lines contains _n_ integers _a__i_, 1, _a__i_, 2, ..., _a__i_, _n_ (). If castles _i_ and _j_ are connected by a wall, then _a__i_, _j_ = 1. Otherwise it is equal to 0.
It is guaranteed that _a__i_, _j_ = _a__j_, _i_ and _a__i_, _i_ = 0 for all 1 ≤ _i_, _j_ ≤ _n_.
## Output
Print the maximum possible sum of stabilities of the walls that Sir Jaime Lannister can achieve.
Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Namely: let's assume that your answer is _a_, and the answer of the jury is _b_. The checker program will consider your answer correct, if .
[samples]
## Note
In the first sample, we can assign 0.5, 0.5, 0 liters of liquid to castles 1, 2, 3, respectively, to get the maximum sum (0.25).
In the second sample, we can assign 1.0, 1.0, 1.0, 1.0 liters of liquid to castles 1, 2, 3, 4, respectively, to get the maximum sum (4.0)
兰尼斯特王国中有 #cf_span[n] 座城堡，一些城墙连接两座城堡，任意两座城堡之间至多有一堵墙，且没有墙连接城堡与自身。
詹姆·兰尼斯特爵士发现丹妮莉丝·坦格利安即将进攻他的王国，因此他希望保卫王国。他拥有 #cf_span[k] 升一种神秘液体，他希望将这些液体分配给各座城堡，使得每座城堡包含一定量的液体（可能为零或非整数升）。分配完成后，每堵墙的稳定性定义如下：若一堵墙连接两座城堡 #cf_span[a] 和 #cf_span[b]，它们分别含有 #cf_span[x] 和 #cf_span[y] 升液体，则该墙的强度为 #cf_span[x·y]。
你的任务是输出詹姆·兰尼斯特爵士能够达到的最大墙稳定性总和。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 40]，#cf_span[1 ≤ k ≤ 1000]）。
接下来 #cf_span[n] 行，第 #cf_span[i] 行包含 #cf_span[n] 个整数 #cf_span[ai, 1, ai, 2, ..., ai, n]。若城堡 #cf_span[i] 和 #cf_span[j] 之间有墙，则 #cf_span[ai, j = 1]；否则为 #cf_span[0]。
保证对所有 #cf_span[1 ≤ i, j ≤ n]，有 #cf_span[ai, j = aj, i] 且 #cf_span[ai, i = 0]。
请输出詹姆·兰尼斯特爵士能够达到的最大墙稳定性总和。
你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。
具体而言：设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，若 ，则判题程序将认为你的答案正确。
在第一个样例中，我们可以将 #cf_span[0.5, 0.5, 0] 升液体分别分配给城堡 #cf_span[1, 2, 3]，以获得最大总和（#cf_span[0.25]）。
在第二个样例中，我们可以将 #cf_span[1.0, 1.0, 1.0, 1.0] 升液体分别分配给城堡 #cf_span[1, 2, 3, 4]，以获得最大总和（#cf_span[4.0]）。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 40]，#cf_span[1 ≤ k ≤ 1000]）。接下来 #cf_span[n] 行，第 #cf_span[i] 行包含 #cf_span[n] 个整数 #cf_span[ai, 1, ai, 2, ..., ai, n]。若城堡 #cf_span[i] 和 #cf_span[j] 之间有墙，则 #cf_span[ai, j = 1]；否则为 #cf_span[0]。保证对所有 #cf_span[1 ≤ i, j ≤ n]，有 #cf_span[ai, j = aj, i] 且 #cf_span[ai, i = 0]。
## Output
请输出詹姆·兰尼斯特爵士能够达到的最大墙稳定性总和。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。具体而言：设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，若 ，则判题程序将认为你的答案正确。
[samples]
## Note
在第一个样例中，我们可以将 #cf_span[0.5, 0.5, 0] 升液体分别分配给城堡 #cf_span[1, 2, 3]，以获得最大总和（#cf_span[0.25]）。在第二个样例中，我们可以将 #cf_span[1.0, 1.0, 1.0, 1.0] 升液体分别分配给城堡 #cf_span[1, 2, 3, 4]，以获得最大总和（#cf_span[4.0]）
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of castles.
Let $ k \in \mathbb{R}^+ $ be the total amount of liquid available.
Let $ A = (a_{ij}) \in \{0,1\}^{n \times n} $ be the adjacency matrix of the castle network, where $ a_{ij} = 1 $ if there is a wall between castle $ i $ and castle $ j $, and $ a_{ij} = 0 $ otherwise.
Let $ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}_{\geq 0}^n $ be the vector of liquid amounts assigned to each castle.
**Constraints**
1. $ \sum_{i=1}^n x_i = k $
2. $ x_i \geq 0 $ for all $ i \in \{1, \dots, n\} $
3. $ a_{ij} = a_{ji} $ and $ a_{ii} = 0 $ for all $ i,j \in \{1, \dots, n\} $
**Objective**
Maximize the total stability:
$$
\sum_{1 \leq i < j \leq n} a_{ij} \cdot x_i x_j
$$
API Response (JSON)
{
"problem": {
"name": "E. Mother of Dragons",
"description": {
"content": "There are _n_ castles in the Lannister's Kingdom and some walls connect two castles, no two castles are connected by more than one wall, no wall connects a castle to itself. Sir Jaime Lannister has d",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF839E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are _n_ castles in the Lannister's Kingdom and some walls connect two castles, no two castles are connected by more than one wall, no wall connects a castle to itself.\n\nSir Jaime Lannister has d...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "兰尼斯特王国中有 #cf_span[n] 座城堡，一些城墙连接两座城堡，任意两座城堡之间至多有一堵墙，且没有墙连接城堡与自身。\n\n詹姆·兰尼斯特爵士发现丹妮莉丝·坦格利安即将进攻他的王国，因此他希望保卫王国。他拥有 #cf_span[k] 升一种神秘液体，他希望将这些液体分配给各座城堡，使得每座城堡包含一定量的液体（可能为零或非整数升）。分配完成后，每堵墙的稳定性定义如下：若一堵墙连接两座城堡 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of castles. \nLet $ k \\in \\mathbb{R}^+ $ be the total amount of liquid available. \nLet $ A = (a_{ij}) \\in \\{0,1\\}^{n \\times n} $ be the adja...",
"is_translate": false,
"language": "Formal"
}
]
}