P3225 [HNOI2012]矿场搭建

    • 1.3K通过
    • 3.6K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 Tarjan 割点 深度优先搜索,DFS 2012 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    输入输出格式

    输入格式:

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

    输出格式:

    输入文件中有多少组数据,输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 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

    说明

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

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。