题目

题目背景
在破除了一些封印之后，仍然有很多的封印。看来普通的方法已经行不通了，还有最后一个办法：血祭。以吾之血，浇灌足下之土地，盛放死亡之花。

题目描述
有 $n$ 朵血之花。其中有 $m$ 对 $(a_i,b_i)$，能够提供血祭的能量。即，如果在第 $i$ 朵血之花处，浇灌 ${\omega }_i$ 单位的鲜血，那么血祭的能量就会增加 ${\omega }_{a_i}\times {\omega }_{b_i}$ 。

你只能浇灌最多 $x$ 单位的鲜血，需要最大化血祭的能量。注意 ${\omega }_i$ 可以为实数。

数据范围与提示
$n⩽40$ 且 $m⩽\frac{n(n-1)}{2}$，而 $x⩽100$ 。

思路

用调整法可知，可以让两个 $\omega \ne 0$ 的值满足周围点的 $\sum \omega$ 相同。

然而我没想到的是：如果二者不相邻，那么即使周围点的 $\sum \omega$ 相同，也可以让其中一个为 $0$，另一个为 ${\omega }_1+{\omega }_2$ 。也就是说，所有非零点都相邻。

相当于就是个团呗！那么大小为 $k$ 的团的最优方案肯定是 $\omega =\frac{x}{k}$，因为任意点的贡献是 ${\omega }_i(x-{\omega }_i)$，求和即 $x^2-\sum {\omega }_i^2$，显然是均分 $\omega$ 最优。同时我们也看到，答案就是 $x^2(1-\frac{1}{k})$，这是关于 $k$ 单调的，所以问题转为 求最大团。

很显然，$n⩽40$ 就是要我们折半搜索。时间复杂度 $\mathcal{O}(n{2}^{n/2})$ 。

代码

注意上面那个式子中，每一对被算了两次，输出时除以二即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){int a = 0, c = getchar(), f = 1;for(; !isdigit(c); c=getchar())(c == '-') ? (f = -f) : 0;for(; isdigit(c); c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
void writeint(int x){if(x > 9) writeint(x/10);putchar((x-x/10*10)^48);
}
inline void getMax(int &x,const int &y){if(x < y) x = y;
}const int MAXN = 20;
int ga[1<<MAXN], gb[1<<MAXN], gm[1<<MAXN];
int dpa[1<<MAXN], dpb[1<<MAXN];inline void fuckZxy(int g[],int n){rep(S,1,(1<<n)-1) g[S] = g[S&-S] bitand g[S&(S-1)];
}
void getBool(int g[],int dp[],int n){rep(S,(dp[0]=1),(1<<n)-1)dp[S] = dp[S&(S-1)] and (S&g[S&-S]) == (S&(S-1));
}
void getInt(int dp[],int n){rep(S,0,(1<<n)-1){dp[S] = (-dp[S])&(__builtin_popcount(S));rep(i,0,n-1) getMax(dp[S],(S>>i&1)*dp[S^(1<<i)]);}
}int main(){freopen("nanami.in","r",stdin);freopen("nanami.out","w",stdout);int n = readint(), m = readint();int x = readint(), ans = 0;const int HALF = n>>1;for(int a,b; m; --m){a = readint()-1, b = readint()-1;if(a > b) std::swap(a,b);if(b < HALF) // in left partga[1<<a] |= (1<<b), ga[1<<b] |= (1<<a);else if(HALF <= a){ // in right partgb[1<<(a-HALF)] |= (1<<(b-HALF));gb[1<<(b-HALF)] |= (1<<(a-HALF));}else gm[1<<(b-HALF)] |= (1<<a);}getBool(ga,dpa,HALF); getInt(dpa,HALF);gm[0] = (1<<HALF)-1; fuckZxy(gm,n-HALF);getBool(gb,dpb,n-HALF);for(int S=0; S<(1<<(n-HALF)); ++S) if(dpb[S])getMax(ans,__builtin_popcount(S)+dpa[gm[S]]);printf("%.6f\n",x*x*(1-double(1)/ans)/2);return 0;
}

后记

终于，历经重重困难，降临于面前的，旧日支配者 普林斯普！虽然他本不该是这个名称——他的名讳并非人类所能发出的声音，呼之应有雷声。

普林斯普长相似人，却又很难称为人；更像一个黑色的柱子，安静地站着，似乎可以站上两个小时，一言不发。他的肩上——也许那并不应称为肩膀——似乎有一只狗，正大张着嘴，露出锋利的牙。它的牙可以随意切断任何基本粒子所组成的凡间物质。

只是望向普林斯普的双眼，就足以让睫毛挂上冰霜；当开口欲言时，嘴边早已白雪如髭。在寒冷的不断压迫之下，我蜷缩成了一团，越来越冷，越来越小……

再次醒来，海浪扑面，我又躺在小岛的海岸上。岛上光秃秃的，什么也没有。我的船靠在岸边，完好无损。一切就如同我在沙滩上打了个盹。

我站起来，努力回想，想要确定刚才发生了什么。或许我只是做了一场梦？一个很长很长很长，长到我已分不清现实与虚幻的梦？

太阳快要落山了，黑夜将至。我爬上船，发动油门，握住方向盘的一瞬间，我看到手上的一道疤——血祭留下的痕迹。当我触摸它时，脑海中似乎炸响了一句话：

吾重返此地，必以无尽 AK 斩灭人类之希望！

$\underline{\text{WHO AM I? I AM PLERINCIAPAL!}}$

也许，他已经来了，就在我们身边。