1575 . 欸西國的欸西M大賽(Accepted)
TopCoder
Tags
Description
欸西國有n個城市，彼此之間皆有路相通，但這相通的路徑也是唯一的。
今天為了促進民間學術交流，增進居民感情，欸西國政府決定舉辦一場全國性的ACM大賽， 欸西國狂熱的君主卡恩則決定所有城市的居民都需參與此一活動，否則不但要剔除國籍，還要被卡恩親自處以電桌球電一百場的極刑。
總之，現在問題來了。由於經費限制，欸西國只能選擇其中k(k<=n)個城市作為考場，不位在考場的居民則要就近選擇鄰近的考場並前往參加比賽。
卡恩雖然對不肯參加比賽的人絲毫不留情，其實卻還是很體貼廣大老百姓的。他希望能安排這k個賽場，使得「任一城市的居民到達最近考場的距離之最大值」最小。
給定欸西國的地圖(即城市相連情況)以及k，試問在最妥善的安排下，任一城市到達最臨近考場的距離中之最大值最小為何？
Input Format
第一列有三個整數n, m, k，其中n代表城市數量，m代表道路數量。
城市的編號為1到n。
接下來的m列每列有兩個正整數Ai, Bi，代表第i條道路連接城市i和城市Bi。
(1<=Ai, Bi<=n)
Output Format
請輸出任一城市居民到達最近考場距離最大值的最小值。
Sample Input 1
範例輸入1
5 4 2
1 2
2 3
3 4
4 5
範例輸入2
5 4 1
1 2
1 3
1 4
4 5
5 4 2
1 2
2 3
3 4
4 5
範例輸入2
5 4 1
1 2
1 3
1 4
4 5
Sample Output 1
範例輸出1
1
範例輸出2
2
1
範例輸出2
2
Hints
至少有30%的測試資料中，n不超過20。
至少有40%的測試資料中，欸西國的所有城市連成了一條直線。
至少有60%的測試資料中，n不超過5,000。
對於所有測試資料而言，n不超過1,000,000。
Problem Source
原TIOJ1575 / 97建中校內資訊能力競賽(prob6)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |