[理工] 最小負環屬於p嗎？怎麼求?

[s89162504 (阿本)]

http://i.imgur.com/oPernYd.jpg

想請問第六題的b

直覺想是所有邊權重乘-1

然後求最大正環

可是感覺跟最長路一樣是npc耶

我是不是誤解了什麼

想請問這個n三方logn的算法？

感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.241.144
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486371341.A.107.html
→ YuxiWen: 是求 最短的負環 才對
→ YuxiWen: 你的想法是在求負最多大的環
推 joeboy: 問一下最小長度的負環，如果我一直繞這個cycle不是會得到
→ joeboy: 更短的環嗎？
→ argorok: 這題是最少求edge的負環
→ yupog2003: 就是一個圖裡面可能有好多好多的負環，找出邊數最少的
→ yupog2003: 那一個，請他出列
→ yupog2003: 而不是找出weight最小的那一個
→ YuxiWen: 網路上找到的 http://i.imgur.com/EvQhV4c.jpg
推 HEroKuma: 借問一下怎麼解跟證背包問題的近似演算法 用Greedy可以
→ HEroKuma: 嗎？