某岛

… : "…アッカリ~ン . .. . " .. .
September 10, 2012

HDU 3435. A new Graph Game

Brief description:

… 无向图最小哈密顿环覆盖。

Analysis:

。。将原图中的每个点拆成左右两部,则一个匹配方案对应一组哈密顿环覆盖。。

。KM。/。(TLE。。
。。。KM。/。(3000ms+。。
(Mark:。。!!居然第三种 KM 写法会比第二种慢。。(看来是 delta 没有达到下界。。。。

External link:

http://acm.hdu.edu.cn/showproblem.php?pid=3435
http://en.wikipedia.org/wiki/Hamiltonian_path