j008: 小老鼠走迷宫
Tags :
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-31 17:05

Content

科學家軒教授要來研究小老鼠的行為,於是他準備了一個迷宫 (宫≠宮),迷宫由 $n$ 個隔間和 $m$ 個單向通道組成,每個通道連接兩個不同隔間,且兩個隔間之間最多只會由一個通道連接。為了不讓小老鼠太累,保證從迷宫裡的其中一個隔間出發,沒有辦法經過一系列的通道回到原本的隔間。

如果有一隻小老鼠到了一個沒有被其他小老鼠走過的隔間,那這隻小老鼠就會在這個隔間留下氣味,宣告這裡是自己的地盤,之後的小老鼠都無法進入此隔間。

軒教授總共會放 $k$ 次小老鼠到迷宫裡,每次他可以選擇將小老鼠放到任何一個隔間裡。小老鼠到了隔間裡後,如果沒有通道可以繼續走或是連接到的隔間都被其他小老鼠走過了,那軒教授就會把這隻小老鼠抓起來,否則軒教授會按照自己的意思將小老鼠引到其中一個通道,讓小老鼠走到下一個沒有小老鼠走過的隔間。

由於軒教授每天有十篇論文要寫,所以沒有那麼多時間,請你幫他找出最小的 $k$ 使得放完 $k$ 次小老鼠後,在軒教授適當的引導下,所有隔間都被小老鼠走過。

Input

第一行有兩個非負整數 $n, m$,代表有 $n$ 個隔間和 $m$ 條通道。

接下來 $m$ 行,每行有兩個正整數 $a, b$,代表此單向通道由隔間 $a$ 向隔間 $b$ 連接。

  • $1\leq n\leq 500$
  • $0\leq m\leq \frac{n\times(n-1)}{2}$
  • $1\leq a,b\leq n$
Output

輸出一個整數 $k$,代表軒教授最少要放 $k$ 次小老鼠才可以把迷宫所有隔間裡的起士吃完。

Sample Input #1
5 5
4 5
5 2
4 2
3 2
4 3
Sample Output #1
3
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (5%): 2.0s , <1K
不公開 測資點#1 (5%): 2.0s , <1M
不公開 測資點#2 (5%): 2.0s , <1M
不公開 測資點#3 (5%): 2.0s , <1M
不公開 測資點#4 (5%): 2.0s , <1M
不公開 測資點#5 (5%): 2.0s , <1M
不公開 測資點#6 (5%): 2.0s , <1K
不公開 測資點#7 (5%): 2.0s , <1M
不公開 測資點#8 (5%): 2.0s , <1K
不公開 測資點#9 (5%): 2.0s , <1M
不公開 測資點#10 (5%): 2.0s , <1M
不公開 測資點#11 (5%): 2.0s , <1K
不公開 測資點#12 (5%): 2.0s , <1K
不公開 測資點#13 (5%): 2.0s , <1K
不公開 測資點#14 (5%): 2.0s , <1K
不公開 測資點#15 (5%): 2.0s , <1K
不公開 測資點#16 (5%): 2.0s , <1M
不公開 測資點#17 (5%): 2.0s , <1M
不公開 測資點#18 (5%): 2.0s , <1M
不公開 測資點#19 (5%): 2.0s , <1M
Hint :

以下為範例一的迷宫,第一張圖為原本隔間與通道的樣子,第二張圖為每個隔間分別被哪些小老鼠走過,最少需要 $3$ 隻小老鼠才可以讓所有隔間被走到。

Tags:
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」