[DFS][重心]1444 - 郵局設置問題

Shaymin · 發表於 2015-2-9 13:38:10

趕快加入我們來參與討論吧！

您需要登錄才可以下載或查看，沒有帳號？加入我們

x

本帖最後由 Shaymin 於 2015-2-9 14:21 編輯

原題：http://tioj.ck.tp.edu.tw/problems/1444
AC：http://tioj.ck.tp.edu.tw/submissions/9030

網路上一堆作法，還樹形DP看了真麻煩ZZZ。

要求有兩項：
最遠的一戶人家家裡的距離最短：樹的重心。
從郵局到最遠的一戶人家家裡的距離最遠的地點：由重心DFS最深處的點。

可以證明一個樹的重心最多只有兩個。找重心做兩次DFS就可以了，各種亂DFS就拿Topcoder......

後面的code很醜，因為一開始想錯一些東西，用硬修補的方法來修......

遊客，本帖隱藏的內容需要積分高於 1 才可瀏覽，您當前積分為 0

[TIOJ] [DFS][重心]1444 - 郵局設置問題

趕快加入我們來參與討論吧！

瀏覽過的版塊