Re: [請益] The Maximum Independent Set Problem
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/02/25 13:53)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
※ 引述《bleed1979 (十三)》之銘言：
: 參考 http://www.dharwadker.org/independent_set/
: 並根據演算法實作自己的版本。
: http://codepad.org/smRwl6MZ
: http://pastie.org/3451941
: 測試題目是SPOJ3196
: http://www.spoj.pl/problems/DIVREL/
: 目前仍是TLE。
: 想請教有沒有更快的演算法，謝謝。
谷歌之後發現這題解法根本就不是最大團
http://rsujskf.blog32.fc2.com/blog-entry-1446.html
不整除關係的最大團 = 整除關係（補圖）的最大獨立集
整除關係是個DAG，而且還是Transitive Closure
因此整除關係的最大獨立集 = 最小路徑覆蓋
又由於是DAG，最小路徑覆蓋 = 最大二分匹配 = 最大流
所以可以用最大流演算法解決這一題
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.131.232
※ 編輯: DJWS 來自: 61.230.131.232 (02/25 13:57)
※ 編輯: DJWS 來自: 61.230.131.232 (02/25 14:25)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
