查看: 974|回復: 0

[HOJ] [POI 13 Stage 2]101 - 捷運路線 (Subway)

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2015-3-24 14:29:33 | 顯示全部樓層 |閱讀模式

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

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

    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,會發現如下圖方法修改,可使答案增加,所以原來方法並非最佳答案。
    065.png
    第二步要證明的是對新建的圖擴張兩次,可使用P鏈的方法擴張為用P+1鏈的方法。有兩種情況:新點-舊點-新點、舊點-新點-新點:擴張的路線圖如下(待補)


    第三步:P鏈到P+1鏈擴張最多只能有兩次。
    第四步:點權重必由點權最大的的點向外(child)嚴格遞減,所以我們每次擴張時,選擇向外延伸的點權最大的點任意一個都是最佳解,所以我們只要貪心選擇權值最大的就是最佳解,並能推到P+1的最佳解。實現大概如下附的Code
    [sojcodepad]2845acba[/sojcodepad]

    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表