某島

… : "…アッカリ~ン . .. . " .. .
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