作者DJWS (...)
看板Prob_Solve
标题Re: [请益] The Maximum Independent Set Problem
时间Sat Feb 25 13:53:15 2012
※ 引述《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)