[問題] ZeroJudge-d688(已解決)

作者: fatcat8127 (胖胖貓)   2019-03-27 18:21:27
關於這題的作法一開始是想從旅行推銷員的方式將所有相互連通的點,以狀態壓縮方式更新
狀態。
感謝cutecpu大大的協助。
解法的核心是利用動態規劃的狀態轉移,枚舉所有的狀態,針對現在的狀態找到一條存在的
邊,邊的一點在集合中另一點不在時就可以狀態轉移。
cutecpu大大的做法巧妙在在判斷上述條件是否存在時是O(n)而不是枚舉任兩個點的邊。
保留錯誤的Code(https://www.codepile.net/pile/P2JW1nq5)
以下是用土炮方式撈出來的第二筆測資:
第二筆測資的答案是84
7 10
2 5
4 7
2 4
6 2
7 3
7 1
6 5
7 5
1 2
5 3
作者: cutekid (可愛小孩子)   2019-03-27 20:05:00
http://codepad.org/gNZ7n7aK ←修改過後 AC 的 C 程式碼

Links booklink

Contact Us: admin [ a t ] ucptt.com