最优方案一定是选择一个团，并在团里平均分配点权。
实际上，定义一个点 \(u\) 的权重 \(w_u\) 为 \(\sum\limits_{(u,v)}s_v\)，那么如果方案中 \(w_x>w_y\)，将 \(y\) 去掉并将其点权加在 \(x\) 上一定更优，所以答案一定会被调整成一个团。
对于求最大团，只需要 meet in the middle 加上高维前缀和就能做到 \(O(n2^n)\)，可以通过。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
inline ll read() {
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=41,S=(1<<20)+5;
int n,k,e11[S],e21[S],e22[S];
bool f1[S],f2[S],e[N][N];
int mx2[S];
int lowbit(int x) {return x&(-x);}
int solve() {
int n1=(n+1)>>1,n2=n-n1;
for(int i=1;i<=n1;i++)
for(int j=1;j<=n1;j++)
if(e[i][j]) e11[1<<(i-1)]|=(1<<(j-1));
for(int i=n1+1;i<=n;i++) {
for(int j=1;j<=n1;j++) if(e[i][j]) e21[1<<(i-n1-1)]|=(1<<(j-1));
for(int j=n1+1;j<=n;j++) if(e[i][j]) e22[1<<(i-n1-1)]|=(1<<(j-n1-1));
}
f1[0]=f2[0]=1;
for(int i=1;i<=n1;i++) f1[1<<(i-1)]=1;
for(int i=1;i<=n2;i++) f2[1<<(i-1)]=1;
for(int i=1;i<(1<<n1);i++) if(i^lowbit(i)) f1[i]=(f1[i^lowbit(i)]&((e11[lowbit(i)]&(i^lowbit(i)))==(i^lowbit(i))));
for(int i=1;i<(1<<n2);i++) if(i^lowbit(i)) f2[i]=(f2[i^lowbit(i)]&((e22[lowbit(i)]&(i^lowbit(i)))==(i^lowbit(i))));
for(int i=0;i<(1<<n2);i++) if(f2[i]) for(int j=1;j<=n2;j++) if(i&(1<<(j-1))) mx2[i]++;
for(int i=1;i<=n2;i++)
for(int j=0;j<(1<<n2);j++)
if(j&(1<<(i-1))) mx2[j]=max(mx2[j],mx2[j^(1<<(i-1))]);
int ans=0;
for(int i=0;i<(1<<n1);i++) {
if(!f1[i]) continue;int s=0,sz=0;
for(int j=1;j<=n1;j++) if(i&(1<<(j-1))) sz++;
for(int j=1;j<=n2;j++) if((i&e21[1<<(j-1)])==i) s|=(1<<(j-1));
ans=max(ans,sz+mx2[s]);
}
return ans;
}
int main() {
n=read(),k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
e[i][j]=read();
int num=solve();
db ans=1.0*k*k*(num-1)/2.0/num;
printf("%.10lf\n",ans);
return 0;
}