#PQJ164x521. QOJ 164_521

    ID: 2679 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2018数学

QOJ 164_521

防御网络 (defense) 防御网络 (defense) 【故事背景】 虽然成功得到了外星人的进攻计划,但JYY 意外地发现,外星母舰对地球 的攻击竟然是随机的!必须尽快在地球上部署防御网络,抵御外星人母舰的攻击。 【问题描述】 地球上的防御网络由节点和节点之间的能量连接组成,防御网络可以看成是 一个𝑛个点、𝑚条边的简单无向图𝐺(𝑉, 𝐸),每个防御节点对应𝑉中的一个节点、每 个能量连接对应𝐸中的一条边。此外,在防御网络修建时考虑到能量传输效率, 防御网络𝐺中每个节点至多只包含在一个简单环中。 外星母舰的攻击是随机的,每次攻击开始后,JYY 都会本次攻击的情况选 择一些防御节点𝑆⊆𝑉,并且用能量连接将这些防御节点连通,从而启动一个防 御子网络。换言之,JYY 会选择𝐺中边集的一个子集𝐻(𝑆) ⊆𝐸,它满足:

  1. (防御子网络连通) 如果我们建立新图𝐺′=𝑉, 𝐻(𝑆)>,即用𝐻(𝑆)中的边连接 𝐺中的节点,则对于任意选择的防御节点𝑥, 𝑦∈𝑆,它们在𝐺′中都连通。
  2. (防御子网络最小) 在满足条件1 (防御子网络连通)的前提下,选取的边 数最小,即|𝐻(𝑆)|最小。 𝐻(𝑆)是点集𝑆在图𝐺生成的斯坦纳树(Steiner Tree),而|𝐻(𝑆)|则是启动防御 子网络的最小代价。考虑到外星母舰随机攻击的方式,JYY 希望你计算启动防 御子网络代价的期望: 1 2|C| D |𝐻(𝑆)| E⊆C

【输入格式】 输入第一行两个整数𝑛, 𝑚,分别表示图中的节点数和边数。 接下来𝑚行,每行两个整数𝑢, 𝑣 (1 ≤𝑢, 𝑣≤𝑛),表示图中的一条边。输入保 证没有自环和重边,并且满足每个节点至多包含在一个简单环中。

防御网络 (defense) 【输出格式】 输出一行,表示启动防御子网络的期望。假设期望写成最简分式𝑃/𝑄的形式, 则输出𝑃⋅𝑄JK mod 1,000,000,007 的余数,其中𝑄JK为唯一的整数满足𝑄⋅𝑄JK ≡ 1 mod 1,000,000,007。 【样例输入1】 3 2 1 2 2 3 【样例输出1】 750000006 【样例输入2】 6 6 1 2 2 3 3 1 1 4 2 5 3 6 【样例输出2】 468750006 【样例说明】 样例输入1 是一条链,包含以下情况: • {}, {1}, {2}, {3},|𝐻(𝑆)| = 0; • {1, 2}, {2, 3}, |𝐻(𝑆)| = 1; • {1, 3}, {1, 2, 3}, |𝐻(𝑆)| = 2。 因此𝑃/𝑄= 3/4,𝑄JK = 250,000,002,𝑃⋅𝑄JK = 750,000,006。 样例输入2 中∑ |𝐻(𝑆)| E⊆C = 174,因此𝑃/𝑄= 87/32,𝑄JK = 281,250,002, 𝑃⋅𝑄JK = 468,750,006 mod 1,000,000,007。

防御网络 (defense) 【数据规模】 对于20%的数据,有1 ≤𝑛≤8。 对于40%的数据,有1 ≤𝑛≤20。 对于100%的数据,有1 ≤𝑛≤200。