[理工] 102中央演算法兩題

[ANANquenchan (ananquenchana)]

第一大題
https://i.imgur.com/P2iTx3n.jpg
https://i.imgur.com/5M7r35s.jpg
第二大題
https://i.imgur.com/pVt9CRL.jpg
翻遍離散跟演算法的書還是沒有想法
求強人指點迷津

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.13.36.215
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543830342.A.309.html
推 kcilao110779: (a) 每個graph不是tree就是有cycle的圖，分為這兩
→ kcilao110779: 種case討論應該就可以了
推 kcilao110779: https://i.imgur.com/Ouy93Ls.jpg
推 FRAXIS: 第二大題應該 greedy 就可解了吧
→ ANANquenchan: 想問k大，可是題目裡面有說要証如果G非tree則G/v要d
→ ANANquenchan: isconnect
→ ANANquenchan: 那應該是在G為cycle的情況下挑cycle某一點有與G圖
→ ANANquenchan: 中的其他點相連之點移除才使G/v disconnect
→ ANANquenchan: 啊沒事我業障重看錯題意
→ ANANquenchan: 謝謝k大跟F大