← 返回题目列表

AtCoder · abc244_f

I. 最短好路径

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个简单的连通无向图 N 顶点和 M 边缘。 (如果图没有多边且没有自环,则称其为简单图。)
对于 i = 1, 2, \ldots, M, i第一条边连接顶点 u_i 和顶点 v_i.

一个序列 (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 是一个长度的字符串 N 组成 0 和 1。 一条路 A = (A_1, A_2, \ldots, A_k) 据说是 好路 关于 S 如果满足以下条件:

  • 对于所有人 i = 1, 2, \ldots, N,认为:
    • if s_i = 0,那么 A 有偶数个 i的。
    • if s_i = 1,那么 A 有奇数个 i的。

有 2^N 可能 S (换句话说,有 2^N 长度的字符串 N 组成 0 和 1)。 求“最短好路径的长度”之和 S“超过所有这些 S.

在本问题的约束下,可以证明,对于任意字符串 S 长度 N 组成 0 和 1,至少有一条关于 S.

约束

  • 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

输出

打印答案。


示例输入 1

3 2
1 2
2 3

示例输出 1

14
  • 对于 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.


示例输入 2

5 5
4 2
2 3
1 3
2 1
1 5

示例输出 2

108