令 \(s_u\) 为点 \(u\) 分配到的权值。
结论：最后选出来有权值的肯定是一个最大团。
考虑反证，如果 \(x, y\) 间没有连边，则 \(x, y\) 的贡献是独立的，若 \(\sum\limits_{(u, x)\in E} s_u\ge \sum\limits_{(v, y) \in E} s_v\)，那么就可以把 \(s_y\) 给 \(s_x\)，否则把 \(s_x\) 给 \(s_y\)，显然这是不劣的。
考虑最后选出来的最大团，使其收益最大的方式肯定是平均。
还是考虑反证，考虑 \(s_x\not = s_y\)，那么对于 \(z\not = x, z\not = y\)，贡献就是 \((s_x + s_y)s_z\)，而 \(x, y\) 的贡献是 \(s_x s_y\)。
那么和不变取平均更优。
最后考虑求解最大团。
考虑直接暴搜，记 \(f_S\) 为点集为 \(S\) 的最大团大小。
那么找到 \(S\) 中最小的点 \(p\)，那么就有 \(2\) 种可能，去掉点 \(p\) 或者选上点 \(p\)。
就有 \(f_{S} = \max\{f_{S - \{p\}}, f_{S\operatorname{bitand} E_p} + 1\}\)，\(E_p\) 为 \(p\) 的边集。
考虑记忆化搜索，这样的复杂度是对的。
复杂度的证明：
考虑根据 \(\min\{S\}\) 来讨论。
如果 \(\min\{S\}> \frac{n}{2}\)，可能有值的位就只会有后面 \(\frac{n}{2}\) 个位。有 \(O(2^\frac{n}{2})\) 种状态。
如果 \(\min\{S\}\le \frac{n}{2}\)，则因为每次取的是最小的点 \(p\)，选完一个点的状态这个点就会变为 \(0\)，只会跟前 \(\min\{S\} - 1\) 个点的选取状态有关，最多也就会有 \(O(2^\frac{n}{2})\) 个状态。
于是用 map 存下所有状态的复杂度是对的。
时间复杂度 \(O(n^2 + 2^\frac{n}{2}n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
std::map<i64, int> f;
i64 to[40];
int dfs(i64 s) {
if (! s) return 0;
if (f.count(s)) return f[s];
int p =__builtin_ctzll(s);
return f[s] = std::max(dfs(s ^ (1ll << p)), dfs(s & to[p]) + 1);
}
int main() {
int n, k; scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int x; scanf("%d", &x);
x && (to[i] |= 1ll << j);
}
int c = dfs((1ll << n) - 1);
printf("%.10lf\n", 1.0 * k * k / c * (c - 1) / 2.0);
return 0;
}