TA的每日心情 | 開心 2015-4-12 10:09 |
---|
簽到天數: 137 天 [LV.7]常住居民III
邁向天堂
蘇多門
- 積分
- 3559
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 domen111 於 2014-11-25 16:01 編輯
http://zerojudge.tw/ShowProblem?problemid=d917
感謝學長的提示「兩個方向的最佳解會不會衝突」,發這篇文讓我自己記一下是怎麼證明最佳解不會衝突的。
做法: 算出兩個方向拓樸深度,相乘就是答案 (當然還要再乘上w*w)
說明:
如圖,黑色代表直向的邊,深度為4,3號、4號、5號在同一層。題目寫說有n(n-1)/2條邊,所以每個點之間一定會存在一條邊。
3、4、5號在同一層 => 3,4,5號之間不可能會有直向的邊 => 3,4,5號之間一定都是橫向的邊 => 3,4,5號之間在橫向時因為之間互相有邊所以不可能在同一層 => 直向層數最少時並不會造成橫向層數增加 => 兩個方向的最佳解不會衝突
隨便寫拓樸排序的AC code:
|
|