103135: [Atcoder]ABC313 F - Flip Machines
Description
Score : $625$ points
Problem Statement
There are $N$ cards numbered $1$ through $N$. Each face of a card has an integer written on it; card $i$ has $A_i$ on its front and $B_i$ on its back. Initially, all cards are face up.
There are $M$ machines numbered $1$ through $M$. Machine $j$ has two (not necessarily distinct) integers $X_i$ and $Y_i$ between $1$ and $N$. If you power up machine $j$, it flips card $X_i$ with the probability of $\frac{1}{2}$, and flips card $Y_i$ with the remaining probability of $\frac{1}{2}$. This probability is independent for each power-up.
Snuke will perform the following procedure.
- Choose a set $S$ consisting of integers from $1$ through $N$.
- For each element in $S$ in ascending order, power up the machine with that number.
Among Snuke's possible choices of $S$, find the maximum expected value of the sum of the integers written on the face-up sides of the cards after the procedure.
Constraints
- $1\leq N \leq 40$
- $1\leq M \leq 10^5$
- $1\leq A_i,B_i \leq 10^4$
- $1\leq X_j,Y_j \leq N$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$
Output
Print the answer. Your output is considered correct if the absolute or relative difference from the true value is at most $10^{-6}$.
Sample Input 1
3 1 3 10 10 6 5 2 1 2
Sample Output 1
19.500000
If $S$ is chosen to be an empty set, no machine is powered up, so the expected sum of the integers written on the face-up sides of the cards after the procedure is $3+10+5=18$.
If $S$ is chosen to be $\lbrace 1 \rbrace$, machine $1$ is powered up.
- If card $X_1 = 1$ is flipped, the expected sum of the integers written on the face-up sides of the cards after the procedure is $10+10+5=25$.
- If card $Y_1 = 2$ is flipped, the expected sum of the integers written on the face-up sides of the cards after the procedure is $10+10+5=25$.
Thus, the expected value is $\frac{25+14}{2} = 19.5$.
Therefore, the maximum expected value of the sum of the integers written on the face-up sides of the cards after the procedure is $19.5$.
Sample Input 2
1 3 5 100 1 1 1 1 1 1
Sample Output 2
100.000000
Different machines may have the same $(X_j,Y_j)$.
Sample Input 3
8 10 6918 9211 16 1868 3857 8537 3340 8506 6263 7940 1449 4593 5902 1932 310 6991 4 4 8 6 3 5 1 1 4 2 5 6 7 5 3 3 1 5 3 1
Sample Output 3
45945.000000
Input
Output
得分：625分
问题描述
有N张卡片，编号为1到N。每张卡片的一面写有一个整数；第i张卡片正面为A_i，背面为B_i。起初，所有卡片都是正面朝上。
有M台编号为1到M的机器。第j台机器有两个（不一定是不同的）整数X_j和Y_j，范围在1到N之间。如果你启动第j台机器，它将以$\frac{1}{2}$的概率翻转卡片X_j，然后以剩余的$\frac{1}{2}$概率翻转卡片Y_j。每次启动的概率是独立的。
Snuke将执行以下过程。
- 选择一个由1到M之间的整数构成的集合S。
- 按照升序顺序，对S中的每个元素，启动对应编号的机器。
在Snuke可能选择的S中，找出过程结束后卡片正面朝上的整数之和的期望值的最大值。
限制条件
- $1\leq N \leq 40$
- $1\leq M \leq 10^5$
- $1\leq A_i,B_i \leq 10^4$
- $1\leq X_j,Y_j \leq N$
- 所有的输入值都是整数。
输入
输入数据通过标准输入给出，格式如下：
$N$ $M$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$
输出
打印答案。如果输出与真实值的绝对差或相对差不超过$10^{-6}$，则认为你的输出是正确的。
样例输入1
3 1 3 10 10 6 5 2 1 2
样例输出1
19.500000
如果选择S为空集，那么没有机器启动，因此过程结束后卡片正面朝上的整数之和的期望值为$3+10+5=18$。
如果选择S为$\lbrace 1 \rbrace$，则启动第1台机器。
- 如果卡片X_1 = 1被翻转，过程结束后卡片正面朝上的整数之和的期望值为$10+10+5=25$。
- 如果卡片Y_1 = 2被翻转，过程结束后卡片正面朝上的整数之和的期望值为$3+6+5=14$。
因此，期望值为$\frac{25+14}{2} = 19.5$。
因此，过程结束后卡片正面朝上的整数之和的期望值的最大值为19.5。
样例输入2
1 3 5 100 1 1 1 1 1 1
样例输出2
100.000000
不同的机器可以有相同的$(X_j,Y_j)$。
样例输入3
8 10 6918 9211 16 1868 3857 8537 3340 8506 6263 7940 1449 4593 5902 1932 310 6991 4 4 8 6 3 5 1 1 4 2 5 6 7 5 3 3 1 5 3 1
样例输出3
45945.000000