#PQJ1198x6312. QOJ 1198_6312
QOJ 1198_6312
NOI2022 省选 DAY1 城市建造(cities) 城市建造(cities) 【题目描述】 在这个国度里面有n 座城市,一开始城市之间修有若干条双向道路,导致这些城市 形成了t ≥2 个连通块,特别的,这些连通块之间两两大小差的绝对值不超过0 ≤k ≤1。 为了方便城市建设与发展,n 座城市中的某t 座城市.在.这t .座.城.市.之.间额外修建了至少 一条双向道路,使得所有城市连通。 现在已经知道额外修建后的所有道路,你需要算出有哪些双向道路集合E′,满足这 些道路有可能是后来额外修建的,请输出答案对998, 244, 353 取模的结果。 即给定一张n 个点m 条边的.无.向.连.通图G = (V, E),询问有多少该图的子图 G′ = (V ′, E′),满足E′̸ = ∅且G −E′ 中恰好有|V ′| 个连通块,且任意两个连通块大小 之差不超过k,保证0 ≤k ≤1,请输出答案对998, 244, 353 取模的结果。 【输入格式】 从文件cities.in 中读入数据。 输入的第一行包含三个正整数n, m, k,分别表示城市数、修建后的道路数以及任意 两个连通块大小之差的上限。 接下来m 行每行包含两个正整数u, v,表示城市u 和v 之间存在一条双向道路,保 证u̸ = v。 【输出格式】 输出到文件cities.out 中。 输出一个数表示答案对998, 244, 353 取模后的结果。 【样例1 输入】 1 4 4 1 2 1 2 3 2 3 4 1 3 5 3 4 【样例1 输出】 1 2 第4 页 共9 页
NOI2022 省选 DAY1 城市建造(cities) 【样例1 解释】 有以下两种情况: • 本来只有(3, 4) 这一条道路,此时有三个连通块,分别为{1}, {2}, {3, 4};后来城 市1, 2, 3 决定在他们三座城市中额外修建了(1, 2), (2, 3), (1, 3) 这三条道路,使得 所有城市连通。 • 本来没有任何道路,此时有四个连通块,分别为{1}, {2}, {3}, {4};后来城市 1, 2, 3, 4 决定在他们四座城市中额外修建了(1, 2), (2, 3), (1, 3), (3, 4) 这四条道路, 使得所有城市连通。 【样例2】 见选手目录下的cities/cities2.in 与cities/cities2.ans。 【样例3】 见选手目录下的cities/cities3.in 与cities/cities3.ans。 【样例4】 见选手目录下的cities/cities4.in 与cities/cities4.ans。 【数据范围】 对于所有的数据,保证:3 ≤n ≤105; n −1 ≤m ≤2 × 105; 0 ≤k ≤1。 测试点 n m k 1, 2 ≤15 ≤20 = 0 3 ∼5 ≤20 ≤50 = 1 6, 7 ≤200 ≤300 = 0 8, 9 ≤2, 000 = n −1 = 1 10, 11 ≤3, 000 = 0 12, 13 = 1 14, 15 ≤105 = n −1 16, 17 ≤2 × 105 = 0 18 ∼20 = 1 第5 页 共9 页