Dotcpp  >  编程题库  >  蓝桥杯算法提高VIP-Tunnels
题目 1947:

蓝桥杯算法提高VIP-Tunnels

时间限制: 2s 内存限制: 192MB 提交: 4 解决: 0

题目描述

一个间谍从你的陷阱中逃出来了,干掉了你的警卫,并且带走了你毁灭世界的计划。你的糟糕的行动由此受到了威胁。现在你需要在他逃出基地之前抓到他。
你的基地由一系列房间和连接它们的双向隧道组成,隧道只在房间处相交。每个房间都配有监控摄像,使你能在任意时刻了解间谍所处的位置。另外,每条隧道里都装有遥控炸药,触发后可以永久毁坏该隧道。间谍在隧道中移动极快,因此你不可能把他困在炸毁的一条隧道中,但你可以炸毁一些隧道,使他无法逃出基地。
显然,间谍不可能逃出基地。所以你的目标是在困住他的同时炸毁最少的隧道,因为之后的重建非常昂贵。找到一种策略,使得在最坏情况下需要炸毁的隧道数最小。

输入格式

输入包含多组数据。每组数据的第一行包含两个整数R, T,分别表示房间的隧道的数量。接下来T行,每行两个整数a, b(0 <= a, b <= R),表示隧道两端的房间编号。形如"0 x"或"x 0"的输入表示联通房间x和基地外部的隧道。
间谍从1出发,你需要阻止他到达点0(基地外部)。

输出格式

对第i组输入,输出"Case $i: ${ans}\n\n",其中${ans}表示对应的答案。
参见样例输出的格式。

样例输入

4 6
1 2
1 3
2 4
3 4
4 0
4 0
4 6
1 2
1 3
1 4
2 0
3 0
4 0
0 0

样例输出

Case 1: 2

Case 2: 2

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签