Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 2730: [HNOI2012]矿场搭建

题目链接

传送门

Description

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

Input

输入文件有若干组数据,每组数据的第一行是一个正整数 N(N≤500),表示工地的隧道数,接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

Output

输入文件中有多少组数据,输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与:之间无空格,: 之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

Sample Input

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

Sample Output

Case 1: 2 4

Case 2: 4 1

HINT

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

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

想说的话

这个题让我更加深切体会到了代码习惯的重要性
本来我是用n作为点数,m作为边数的
这个题由于输入原因我就改变了一下
然后到了后面就乱掉了。。。。。。

题解

由于数据范围小,此题可以暴力。。。
显然若非割点坍塌,就无所谓啦,只要考虑坍塌在割点的情况
删去所有割点得到若干连通块,如果图中只有一个连通块,一共只需要设两个
若一个连通块可以到达两个割点的话则不用设置救援出口,否则要设置一个
割点可以删去点然后遍历图求,复杂度n方
对每个割点划分的各个连通块染色,重复染色记为-1
似乎这全是暴力。。。

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏