竹園論壇

標題: [DFS][重心]1444 - 郵局設置問題 [打印本頁]

作者: Shaymin 時間: 2015-2-9 13:38
標題: [DFS][重心]1444 - 郵局設置問題
本帖最後由 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很醜，因為一開始想錯一些東西，用硬修補的方法來修......

歡迎光臨竹園論壇 (http://forum.tfcis.org/)