102207: [AtCoder]ABC220 H - Security Camera
Description
Score : $600$ points
Problem Statement
AtCoder Town has $N$ intersections and $M$ roads.
Road $i$ connects Intersections $A_i$ and $B_i$.
Takahashi, the mayor, has decided to install zero or more surveillance cameras at the intersections.
Each intersection can be installed with zero or one surveillance camera.
How many of the $2^N$ ways to install surveillance cameras monitor an even number of roads?
Here, Road $i$ is said to be monitored when the following condition is satisfied:
a surveillance camera is installed at one or both of Intersections $A_i$ and $B_i$.
Constraints
- $2 \leq N \leq 40$
- $1 \leq M \leq \frac{N(N-1)}{2}$
- $1 \leq A_i \lt B_i \leq N$
- $(A_i,B_i) \neq (A_j,B_j)$ if $i \neq j$.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$
Output
Print the answer.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
6
The sets of towns to install surveillance cameras to satisfy the condition are: $ \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}$.
Note that it is allowed to install no surveillance camera.
Sample Input 2
20 3 5 6 3 4 1 2
Sample Output 2
458752
The town may not be connected.
Input
题意翻译
给定一个 $n$ 个点 $m$ 条边的无向图, 对于每个点你可以给它安装一个摄像头或是不装, 对于所有 $2^n$ 种方案中, 有多少方案满足有偶数条边被监控到, 一条边被监控的条件为两个端点至少有一个有摄像头.Output
分数:$600$分
问题描述
在AtCoder镇上有$N$个交叉口和$M$条道路。
第$i$条道路连接交叉口$A_i$和$B_i$。
市长Takahashi决定在交叉口安装零个或多个监控摄像头。
每个交叉口可以安装零个或一个监控摄像头。
有多少种安装监控摄像头的方法可以监控偶数条道路?
这里,当满足以下条件时,称道路$i$被监控:
在交叉口$A_i$和$B_i$中的一个或两个安装监控摄像头。
约束条件
- $2 \leq N \leq 40$
- $1 \leq M \leq \frac{N(N-1)}{2}$
- $1 \leq A_i \lt B_i \leq N$
- 如果$i \neq j$,则$(A_i,B_i) \neq (A_j,B_j)$。
- 输入中的所有值都是整数。
输入
从标准输入以以下格式获取输入:
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$
输出
打印答案。
样例输入1
3 2 1 2 2 3
样例输出1
6
满足条件的安装监控摄像头的城镇集合为:$\{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}$。
注意允许不安装监控摄像头。
样例输入2
20 3 5 6 3 4 1 2
样例输出2
458752
城镇可能没有连接。