推 brad84622: 喔喔!! 懂了! 謝謝~! 08/28 02:06
※ 引述《brad84622 (brad84622)》之銘言：
: http://i.imgur.com/gMq2qsZ.jpg
: 想請問w跟s的圖為何一邊是12345呢?
: -----
: Sent from JPTT on my Samsung SM-N9208.
其實他w與s的表格是經過修剪過的版本，如果將原始的寫出來應該會是長這樣
http://imgur.com/kapIMrq
W[i,j]的定義有打在上面了，因為p0不存在所以沒有值
所以W[0,1]~W[0,5]會等於W[1,1]~W[1,5]，也就是說有沒加p0，值都是一樣，
所以i=0那列可以刪掉;j=5那行也可以刪掉（因為沒有p5與q5）。
S[i,j]的定義是ai~aj都當root試試看，找出最小成本的樹，
因為沒有a0所以S[0,1]~S[0,5]會跟S[1,1]~S[1,5]的值一樣，
所以i=0那行刪掉;
j=5那行也可以刪掉（因為沒有a5）。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.100.92
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1472317064.A.880.html