2016年2月25日 星期四

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

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/199_files/extensions/MathMenu.js
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:
TestTimeMemoryScore
0-13000ms131072kb
0-23000ms131072kb
13000ms131072kb10
23000ms131072kb10
33000ms131072kb10
43000ms131072kb10
53000ms131072kb10
63000ms131072kb10
73000ms131072kb10
83000ms131072kb10
93000ms131072kb10
103000ms131072kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原