TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原題:http://hoj.twbbs.org/judge/problem/view/101
AC:http://hoj.twbbs.org/judge/judge/submission/33133
我們先找出直徑上最遠的點R,將R為根作樹鍊剖分,不果剖的是最深的鏈,並將鏈縮成點權為鏈上點數的點。把前[tex]min(C,1+(L-1)*2)[/tex]大的點權加起來就是答案,C是切出的總鏈數。
可以用數學歸納法證明其正確性:
如果L=1,那樹鏈剖分的最長鏈會是樹的直徑長。考慮由P條鏈擴張成P+1條鏈的方法:
新增的一條鏈一定是原有答案鏈的分支,如果P+1鏈的答案不與原有答案相交/臨,考慮該鏈與原有鏈的連線Z,會發現如下圖方法修改,可使答案增加,所以原來方法並非最佳答案。
第二步要證明的是對新建的圖擴張兩次,可使用P鏈的方法擴張為用P+1鏈的方法。有兩種情況:新點-舊點-新點、舊點-新點-新點:擴張的路線圖如下(待補)
第三步:P鏈到P+1鏈擴張最多只能有兩次。
第四步:點權重必由點權最大的的點向外(child)嚴格遞減,所以我們每次擴張時,選擇向外延伸的點權最大的點任意一個都是最佳解,所以我們只要貪心選擇權值最大的就是最佳解,並能推到P+1的最佳解。實現大概如下附的Code
[sojcodepad]2845acba[/sojcodepad]
|
|