[PKUSC2022]撸猫——Hall定理

作为一位喜欢猫的人，小 B 家里养了 n n n 只猫。这些猫从 1 1 1 到 n n n 标号。

他每天最喜欢的时候就是撸猫，可惜猫猫并不是每天都愿意被他撸。愿意被他撸的猫猫集合 S ⊆ [ n ] S subseteq [n] S⊆[n] 根据某个概率分布 P P P 随机而来。 在知道了哪些猫猫愿意被撸之后，小B可以选择某一只愿意的来 rua。注意，如果 S S S 集合为空，则小 B 不能撸任何一只猫。同时，小 B 的撸猫策略可以带有随机性。比如,在知道了 1,2 号猫猫都愿意被撸之后，他可以以 50 % 50% 50% 的概率撸第一只猫，以另外 50 % 50% 50% 的概率撸第二只猫。

作为一位公平的人，小 B 希望给每一只猫猫更多被 rua 的机会。他希望设计一个撸猫的策略来最大化 Pr ⁡ [ i 被撸 ∣ i ∈ S ] operatorname{Pr}[i_{text{被撸}} | iin S] Pr[i被撸​∣i∈S] 的最小值。换句话说，令 p i = Pr ⁡ [ i ∈ S ] p_i = operatorname{Pr}[iin S] pi​=Pr[i∈S] 是第 i i i 只猫猫愿意被撸的概率。我们需要设计一个撸猫的策略来最大化常数 c c c，使得每只猫被撸的概率至少是 c p i cp_i cpi​。

输入格式

一行一个整数 n n n。
一行 2 n 2^n 2n 个浮点数，表示第 i i i 种可能情况的概率。

输出格式

一行一个浮点数 c c c，表示答案。

样例

样例输入 1

2
0.25 0.25 0.25 0.25

样例输出 1

0.7500000000

样例输入 2

3
0.12 0.18 0.02 0.1 0.1 0.05 0.15 0.28

样例输出 2

0.5057471264

数据范围与提示

Subtask 1 [12 pts]： 1 ⩽ n ⩽ 2 1leqslant nleqslant 2 1⩽n⩽2。
Subtask 2 [18 pts]： 1 ⩽ n ⩽ 7 1leqslant nleqslant 7 1⩽n⩽7。
Subtask 3 [10 pts]： 1 ⩽ n ⩽ 10 1leqslant nleqslant 10 1⩽n⩽10。
Subtask 4 [35 pts]： 1 ⩽ n ⩽ 15 1leqslant nleqslant 15 1⩽n⩽15。
Subtask 5 [25 pts]： 1 ⩽ n ⩽ 20 1leqslant nleqslant 20 1⩽n⩽20。

听永神说是脑瘫题。

考虑二分答案，那么问题就转化为一个二分图网络流：左边是 2 n 2^n 2n 个点表示每种情况，入边容量为这种情况的概率，右边是 n n n 个点表示每只猫，出边容量为 c ∗ p i c*p_i c∗pi​，中间对应连上容量 + ∞ +infty +∞ 的边。答案合法当且仅当图的右边满流。

我们可以直接套用 H a l l rm Hall Hall 定理来判断是否可以满流，这样判断一次是 O ( 2 n ) O(2^n) O(2n)，二分答案可以直接通过。

当然你会发现完全没必要二分答案，直接 H a l l rm Hall Hall 定理枚举时取个最小值即可。

我的还是二分答案

#include//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('n')
#define lowbit(x) ((x)&-(x))
#define inline jzm
using namespace std;
const int MAXN=114514;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
const double eps=1e-10;
int n;
double p[25],f[1<<20],g[1<<20],sum;
bool check(double c){
	for(int s=0;s<(1<=sum-f[s^m]+eps)return 0;
	return 1;
}
int main()
{
	n=read();
	for(int s=0;s<(1<>(i-1))&1)p[i]+=f[s];
	for(int k=1;k<(1<
		mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	printf("%.10fn",mid);
	return 0;
}