1375 . 黑色騎士團的最終野望

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

86.7% (13/15)

Submission's AC Ratio

27.1% (32/118)

Tags

CKsum 2008-CKsum-2nd

Description

　　主角威能。屢次阻止了黑色騎士團的第一野望，於是他們想出另種辦法。

　　就是佔據一些城市，使得與城市相連的道路，都可以在他的控制之下。

　　翻開大不列顛帝國的國土，你要找出黑色騎士團最少需要攻佔多少座城市

　　並將結果報告回司令部，好讓司令部擬出對策，打破黑色騎士團的最終野望

Input Format

本題有多筆測試資料，請以EOF作為結束。(測試資料不超過十組)

第一行為兩個數字，n，m分別代表有幾個城市，幾條道路

(0≦n≦20，0≦m≦200)

接著有m行，每行兩個數字，st，ed分別代道路兩端連結的城市編號。

(0≦st，ed≦n-1)

Output Format

輸出黑色騎士團完成野望最小需要攻佔多少城市。

Sample Input 1

5 5
0 4
1 2
1 4
2 4
4 3

Sample Output 1

2

Hints

Problem Source

原TIOJ1375 / (最小頂點覆蓋) Problem Setter：ggm

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
Submit
Back to Top