F - Shortest Good Path

Contest Duration: 2022-03-20(Sun) 12:00 - 2022-03-20(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Shortest Good Path Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N$ 個の頂点と $M$ 本の辺からなる単純（自己ループおよび多重辺を持たない）かつ連結な無向グラフが与えられます。
$i = 1, 2, \ldots, M$ について、 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。

下記の $2$ つの条件をともに満たす整数列 $(A_1, A_2, \ldots, A_k)$ を長さ $k$ のパスと呼びます。

すべての $i = 1, 2, \dots, k$ について、 $1 \leq A_i \leq N$ 。
すべての $i = 1, 2, \ldots, k-1$ について、頂点 $A_i$ と頂点 $A_{i+1}$ は辺で直接結ばれている。

空列も長さ $0$ のパスとみなします。

$S = s_1s_2\ldots s_N$ を $0$ と $1$ のみからなる長さ $N$ の文字列とします。パス $A = (A_1, A_2, \ldots, A_k)$ が下記を満たすとき、パス $A$ を $S$ に関する良いパスと呼びます。

すべての $i = 1, 2, \ldots, N$ について、次を満たす。
- $s_i = 0$ ならば、 $A$ に含まれる $i$ の個数は偶数である。
- $s_i = 1$ ならば、 $A$ に含まれる $i$ の個数は奇数である。

$S$ として考えられる文字列（すなわち、 $0$ と $1$ のみからなる長さ $N$ の文字列）は $2^N$ 個ありますが、そのすべてにわたる「 $S$ に関する良いパスのうち最短のものの長さ」の総和を出力してください。

この問題の制約下において、 $0$ と $1$ からなる長さ $N$ のどのような文字列を $S$ として選んでも、 $S$ に関する良いパスが少なくとも $1$ つ存在することが示せます。

制約

$2 \leq N \leq 17$
$N-1 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq u_i, v_i \leq N$
与えられるグラフは単純かつ連結
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $u_1$   $v_1$ 
 $u_2$   $v_2$ 
 $\vdots$ 
 $u_M$   $v_M$

出力

答えを出力せよ。

入力例 1Copy

Copy

3 2
1 2
2 3

出力例 1Copy

Copy

$S = 000$ のとき、空列 $()$ は $S$ に関する最短の良いパスであり、その長さは $0$ です。
$S = 100$ のとき、 $(1)$ は $S$ に関する最短の良いパスであり、その長さは $1$ です。
$S = 010$ のとき、 $(2)$ は $S$ に関する最短の良いパスであり、その長さは $1$ です。
$S = 110$ のとき、 $(1, 2)$ は $S$ に関する最短の良いパスであり、その長さは $2$ です。
$S = 001$ のとき、 $(3)$ は $S$ に関する最短の良いパスであり、その長さは $1$ です。
$S = 101$ のとき、 $(1, 2, 3, 2)$ は $S$ に関する最短の良いパスであり、その長さは $4$ です。
$S = 011$ のとき、 $(2, 3)$ は $S$ に関する最短の良いパスであり、その長さは $2$ です。
$S = 111$ のとき、 $(1, 2, 3)$ は $S$ に関する最短の良いパスであり、その長さは $3$ です。

よって、求める答えは $0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14$ です。

入力例 2Copy

Copy

出力例 2Copy

Copy

Score : $500$ points

Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $M$ edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For $i = 1, 2, \ldots, M$ , the $i$ -th edge connects Vertex $u_i$ and Vertex $v_i$ .

A sequence $(A_1, A_2, \ldots, A_k)$ is said to be a path of length $k$ if both of the following two conditions are satisfied:

For all $i = 1, 2, \dots, k$ , it holds that $1 \leq A_i \leq N$ .
For all $i = 1, 2, \ldots, k-1$ , Vertex $A_i$ and Vertex $A_{i+1}$ are directly connected by an edge.

An empty sequence is regarded as a path of length $0$ .

Let $S = s_1s_2\ldots s_N$ be a string of length $N$ consisting of $0$ and $1$ . A path $A = (A_1, A_2, \ldots, A_k)$ is said to be a good path with respect to $S$ if the following conditions are satisfied:

For all $i = 1, 2, \ldots, N$ , it holds that:
- if $s_i = 0$ , then $A$ has even number of $i$ 's.
- if $s_i = 1$ , then $A$ has odd number of $i$ 's.

There are $2^N$ possible $S$ (in other words, there are $2^N$ strings of length $N$ consisting of $0$ and $1$ ). Find the sum of "the length of the shortest good path with respect to $S$ " over all those $S$ .

Under the Constraints of this problem, it can be proved that, for any string $S$ of length $N$ consisting of $0$ and $1$ , there is at least one good path with respect to $S$ .

Constraints

$2 \leq N \leq 17$
$N-1 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq u_i, v_i \leq N$
The given graph is simple and connected.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $M$ 
 $u_1$   $v_1$ 
 $u_2$   $v_2$ 
 $\vdots$ 
 $u_M$   $v_M$

Output

Print the answer.

Sample Input 1Copy

Copy

3 2
1 2
2 3

Sample Output 1Copy

Copy

For $S = 000$ , the empty sequence $()$ is the shortest good path with respect to $S$ , whose length is $0$ .
For $S = 100$ , $(1)$ is the shortest good path with respect to $S$ , whose length is $1$ .
For $S = 010$ , $(2)$ is the shortest good path with respect to $S$ , whose length is $1$ .
For $S = 110$ , $(1, 2)$ is the shortest good path with respect to $S$ , whose length is $2$ .
For $S = 001$ , $(3)$ is the shortest good path with respect to $S$ , whose length is $1$ .
For $S = 101$ , $(1, 2, 3, 2)$ is the shortest good path with respect to $S$ , whose length is $4$ .
For $S = 011$ , $(2, 3)$ is the shortest good path with respect to $S$ , whose length is $2$ .
For $S = 111$ , $(1, 2, 3)$ is the shortest good path with respect to $S$ , whose length is $3$ .

Therefore, the sought answer is $0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy