竹園論壇

標題: [成大賽2015]野生題解_2.7182(E~F) [打印本頁]

作者: visitorIKC 時間: 2015-7-9 09:33
標題: [成大賽2015]野生題解_2.7182(E~F)
1. Problem E.冰雪奇緣

題目是給你一個圖,長度小於給定數邊的才能通過
問說一個人是否能從一點走遍全部的邊(可以重複)

其實這題只要直接刪除長度大於給定距離的邊,然後在快樂的判斷一下連通性就可以AC了
完全沒有陷阱,輕鬆AC.

2. Problem F.大家族

題目是給你一個連通的族譜,求他的最大親等
其實這就只是一個基本的樹直徑而已.

2次DFS O(N) 即可解決.

但是你一開始會發現你會WA,然後過一陣子才變成AC.
這是有內情的.話說有一隊拿到WA之後,他們正好有人在UVa上寫過這題,於是Judge就被嗆了(X.
為了不要再被嗆,所以只好把WA改成AC以平息眾怒.(大誤
=========================================
就先這樣啦剩下的以後再看看(?

作者: jd3 時間: 2015-7-9 23:59
補充：

pF 樹直徑詳解

首先是題目的祖譜
雖然說是祖譜但哪一代根本不重要
重點是沒有環，所以是樹

題目找樹上最遠的兩點的距離
也就是所謂「直徑」
這東西有點像有機化學在找最長碳鏈
有認真讀有機化學應該會很有感覺

作法大致長這樣：
1.從任意一點 DFS 找到最遠的點
2.從找到的點再DFS一次，一樣找到最遠的點
3.以上兩個步驟找到的兩點必為其中一條直徑上的兩點

說明(這不是嚴謹的證明, 用詞和符號也不學術)：

以下解釋在邊權>0時才成立

_0：先定義直徑就是最遠兩點間的路徑
_1：直徑不一定只有一條，但都一樣長 ( 廢話 ˋ ˊ )
_2：直徑間必相交於一半長度，或部分重疊
_3：如果有直徑AB，直徑上有一點P，
   A在P左邊(或同點), B在P右邊(或同點)
   P往左走到C的距離|CP|若>|AP|
   則 |CPB| > |APB|, AB就不是直徑
   所以得知C往左走最遠一定是A或距離相同的點(同樣可以當直徑端點)
_4：左右走並沒什麼差別
   所以DFS能走到的最遠的點一定是某個直徑端點
_5：從一個直徑端點能走到最遠的點必然為某個直徑上的另一端點
   否則這個點不可能是直徑上的點(ㄜ...這麼說是為了讓前一段落看不懂還能理解)

綜合以上
DFS第1次找到直徑上某點
第2次找到另一點

長度就是DFS深度

此題結束。

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