[問題] Chinese Postman Man...

看板Prob_Solve作者 (Link)時間19年前 (2006/12/01 22:02), 編輯推噓0(0推 0噓 4→)
留言4則, 1人參與, 最新討論串1/1
我知道要把奇點找出來... 但是奇點與奇點之間的MATCHING跟MIN值 要怎麼在P時間內完成?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.137.46.163
→
12/01 22:29, , 1F
奇點集合 N = min( N-{a,b} + {a,b} )
12/01 22:29, 1F
→
12/01 22:29, , 2F
{a,b}為要MATCH的奇點
12/01 22:29, 2F
→
12/01 22:29, , 3F
所以當下的n個點的結構 要往前找C(n,2)個子結構
12/01 22:29, 3F
→
12/01 22:29, , 4F
這是我後來想的DP 還有什麼更優的方法?
12/01 22:29, 4F
‣ 更多 LinkCar 的文章
文章代碼(AID): #15S3NRMx (Prob_Solve)