題目 1947:
藍(lán)橋杯算法提高VIP-Tunnels
時間限制: 2s
內(nèi)存限制: 192MB 提交: 4 解決: 0
題目描述
一個間諜從你的陷阱中逃出來了，干掉了你的警衛(wèi)，并且?guī)ё吡四銡缡澜绲挠媱潯Ｄ愕脑愀獾男袆佑纱耸艿搅送{?，F(xiàn)在你需要在他逃出基地之前抓到他。
你的基地由一系列房間和連接它們的雙向隧道組成，隧道只在房間處相交。每個房間都配有監(jiān)控攝像，使你能在任意時刻了解間諜所處的位置。另外，每條隧道里都裝有遙控炸藥，觸發(fā)后可以永久毀壞該隧道。間諜在隧道中移動極快，因此你不可能把他困在炸毀的一條隧道中，但你可以炸毀一些隧道，使他無法逃出基地。
顯然，間諜不可能逃出基地。所以你的目標(biāo)是在困住他的同時炸毀最少的隧道，因為之后的重建非常昂貴。找到一種策略，使得在最壞情況下需要炸毀的隧道數(shù)最小。
輸入格式
輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行包含兩個整數(shù)R, T，分別表示房間的隧道的數(shù)量。接下來T行，每行兩個整數(shù)a, b(0 <= a, b <= R)，表示隧道兩端的房間編號。形如"0 x"或"x 0"的輸入表示聯(lián)通房間x和基地外部的隧道。
間諜從1出發(fā)，你需要阻止他到達(dá)點0（基地外部）。
輸出格式
對第i組輸入，輸出"Case $i: ${ans}\n\n"，其中${ans}表示對應(yīng)的答案。
參見樣例輸出的格式。
樣例輸入
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
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點擊這里了解課程詳情