發表新討論
#13116: O(mn)演算法


xavier13540 (柊 四千)

學校 : 國立臺灣大學
編號 : 21783
來源 : [36.230.29.43]
最後登入時間 ：
2024-07-06 14:41:17
b992. 欸肥宅快去運動啦! -- 經典問題 | From: [140.112.229.87] | 發表日期 : 2017-12-11 05:49

我出這題的目的在推廣發表在SODA 17上的帶權有向圖最小環的O(mn)演算法
這個演算法的精神是找上界並剪枝 把Johnson演算法的時間複雜度由O(mn log n)降為O(mn)
因為我懶得把演算法打在這邊 請有興趣的人直接參考下面的論文
http://www.optimization-online.org/DB_FILE/2016/02/5321.pdf

另外 為了卡掉O(mn log n)的解 只好請寫O(mn)演算法的人讓自己的程式跑快點囉wwwwww

 
#13144: Re:O(mn)演算法


310573sao (Jiburiru)

學校 : 新北市立板橋高級中學
編號 : 48055
來源 : [59.127.176.2]
最後登入時間 ：
2020-04-01 20:44:03
b992. 欸肥宅快去運動啦! -- 經典問題 | From: [220.135.171.68] | 發表日期 : 2017-12-17 19:54

我出這題的目的在推廣發表在SODA 17上的帶權有向圖最小環的O(mn)演算法
這個演算法的精神是找上界並剪枝 把Johnson演算法的時間複雜度由O(mn log n)降為O(mn)
因為我懶得把演算法打在這邊 請有興趣的人直接參考下面的論文
http://www.optimization-online.org/DB_FILE/2016/02/5321.pdf

另外 為了卡掉O(mn log n)的解 只好請寫O(mn)演算法的人讓自己的程式跑快點囉wwwwww


英文論文...好困難

 
#13557: Re:O(mn)演算法


xavier13540 (柊 四千)

學校 : 國立臺灣大學
編號 : 21783
來源 : [36.230.29.43]
最後登入時間 ：
2024-07-06 14:41:17
b992. 欸肥宅快去運動啦! -- 經典問題 | From: [140.112.229.87] | 發表日期 : 2018-03-18 02:24

我出這題的目的在推廣發表在SODA 17上的帶權有向圖最小環的O(mn)演算法
這個演算法的精神是找上界並剪枝 把Johnson演算法的時間複雜度由O(mn log n)降為O(mn)
因為我懶得把演算法打在這邊 請有興趣的人直接參考下面的論文
http://www.optimization-online.org/DB_FILE/2016/02/5321.pdf

另外 為了卡掉O(mn log n)的解 只好請寫O(mn)演算法的人讓自己的程式跑快點囉wwwwww

如果覺得論文字太多看不下去卻又想知道怎麼做
我把演算法整理在這邊
有興趣的就自己看囉><

 
#13720: Re:O(mn)演算法


xavier13540 (柊 四千)

學校 : 國立臺灣大學
編號 : 21783
來源 : [36.230.29.43]
最後登入時間 ：
2024-07-06 14:41:17
b992. 欸肥宅快去運動啦! -- 經典問題 | From: [140.112.229.87] | 發表日期 : 2018-04-14 04:39

另外 為了卡掉O(mn log n)的解 只好請寫O(mn)演算法的人讓自己的程式跑快點囉wwwwww

似乎有人努力寫了$O(mn)$的解卻在第二筆吃了TLE
其實可以設個門檻$c \in (0, 1)$
當$m>cn^2$時 用Floyd-Warshall演算法來計算答案

另外 我寫了一個時間複雜度$O(mn\log n)$的演算法並悲劇(?)地AC這題了 囧

 
#14031: Re:O(mn)演算法


kkmomo (kkmomo)

學校 : 不指定學校
編號 : 29247
來源 : [223.137.94.20]
最後登入時間 ：
2024-06-28 12:05:12
b992. 欸肥宅快去運動啦! -- 經典問題 | From: [114.24.134.204] | 發表日期 : 2018-06-02 17:38

我出這題的目的在推廣發表在SODA 17上的帶權有向圖最小環的O(mn)演算法
這個演算法的精神是找上界並剪枝 把Johnson演算法的時間複雜度由O(mn log n)降為O(mn)
因為我懶得把演算法打在這邊 請有興趣的人直接參考下面的論文
http://www.optimization-online.org/DB_FILE/2016/02/5321.pdf

另外 為了卡掉O(mn log n)的解 只好請寫O(mn)演算法的人讓自己的程式跑快點囉wwwwww

原論文中Figure 3. Procedure Min-Length-Cycle(s) 裡的 Distance-Update(s; j); 是不是縮排錯了，

如果 Distance-Update 放在 if 中結果會不正確。

同樣 Figure 3. 中 If (mldc > ds(j) + c_js)) Then 的右括號不知是多打的還是有漏印條件

if 條件應該要是 "s 是 j 的 successors" 且 "mldc > ds(j) + c_js" 不然 c_js 根本沒定義，對吧?

 
ZeroJudge Forum