比赛场次 456
比赛名称 不准粘代码,必须自己写(HS除外)
比赛状态 已结束比赛成绩
开始时间 2019-09-27 19:00:00
结束时间 2019-09-27 21:46:00
开放分组 全部用户
注释介绍
题目名称 矿场搭建
输入输出 bzoj_2730.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar梦那边的美好ET AAAAAAAAAA 0.005 s 13.68 MiB 100

矿场搭建

★★★   输入文件:bzoj_2730.in   输出文件:bzoj_2730.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。(注:根据数据,此处无向图保证初始连通)by wzw

为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

【输入格式】

输入有若干组数据。

每组数据的第一行是一个正整数 $N$,表示工地的隧道数。

接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$,表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。

输入数据以 $0$ 结尾。

【输出格式】

输出有若干行。

其中第 $i$ 行以 $Case\ i:$ 开始(注意大小写,$Case$ 与 $i$ 之间有空格,$i$ 与 $:$ 之间无空格,$:$ 之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 $2^{64}$。

输出格式参照以下输入输出样例。

【样例1输入】

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

【样例1输出】

Case 1: 2 4
Case 2: 4 1

【样例2】

点击下载样例2

【样例1说明】

$Case\ 1$ 的四组解分别是 $(2,4),(3,4),(4,5),(4,6)$;

$Case\ 2$ 的一组解为 $(4,5,6,7)$。

【样例2】

对于 $10\%$ 的数据,$N \leq 10$。

对于 $70\%$ 的数据,$数据组数 = 1$。

对于 $100\%$ 的数据,$数据组数 \leq 3,N \leq 300$。