[HOJ 199][COI 2012]KAMPANJA (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/199_files/extensions/MathMenu.js

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 199 - KAMPANJA

Problem Statistics

Solved Member: 10　　Submission: 28　　User Tried: 10

Problem：

大選接近了，因此 Amabo Kcarab 總統準備要去 WDC 和 LA 兩地演講。為了要給總統足夠的保安資源，特工必須持續的監控所有總統會經過的城市。

當然，聯邦預算必須被合理的使用，因次總統並不會搭乘 AirForce-1(空軍一號)，而會搭乘一般的車子。而總統車隊的路線是由這群特工規劃的，從 WDC 出發經過 LA，再從 LA 回到 WDC，這樣才能確保特工必須監控的城市數量最少。

對於這個問題，總共有 N 個城市，這些城市的編號從 1~N，另外有 M 條單向道路。WDC 的編號為 1，而 LA 為 2。

請你寫一支程式計算最少需要被監控的城市數量，你所規劃的道路必須經過 WDC 和 LA，再回到 WDC。

Input：

第一行包含兩個整數 N 和 M(2 ≤ N ≤ 100, 2 ≤ M ≤ 200)，代表城市數量和單向道路數量。

接下來的 M 行，每行有兩個整數A, B(1 ≤ A, B ≤ N)，不會有重複的路徑，但可能會存在兩個城市由相反方向互相連通。〈注意本題為單向道路〉

註：測資保證一定存在至少一組路徑滿足題敘。

Output：

請輸出唯一一行，包含一個整數，代表最少需要監控的城市數量。

Sample Input：

SAMPLE A:
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3

SAMPLE B:
9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1

Sample Output：

SAMPLE A:
6

SAMPLE B:
6

HINT：

佔本題 20% 的測資，N 最大為 20。

對於第一筆範例測資，總統可以經過這樣的路徑：1 -> 3 -> 4 -> 2 -> 6 -> 3 -> 4 -> 5 -> 1。因此，他需要經過的城市數量最少為6。

Source：

COI 2012

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0-1	3000ms	131072kb
0-2	3000ms	131072kb
1	3000ms	131072kb	10
2	3000ms	131072kb	10
3	3000ms	131072kb	10
4	3000ms	131072kb	10
5	3000ms	131072kb	10
6	3000ms	131072kb	10
7	3000ms	131072kb	10
8	3000ms	131072kb	10
9	3000ms	131072kb	10
10	3000ms	131072kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。