[問題] ZeroJudge-d688 无向图中子图的个数
看板Prob_Solve (計算數學 Problem Solving)作者fatcat8127 (胖胖貓)時間5年前 (2019/03/27 18:21)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/1
關於這題的作法一開始是想從旅行推銷員的方式將所有相互連通的點，以狀態壓縮方式更新
狀態。
感謝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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1553682091.A.9E5.html
推
03/27 20:05,
5年前
, 1F
03/27 20:05, 1F
※ 編輯: fatcat8127 (61.231.105.100), 03/28/2019 13:24:47
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
