※ 引述《twohsien (twohsien)》之銘言：
: 我覺得6.8不是optimal解耶
: 第一次移走一個vertex的edge數為 2n
: 但第二次就有可能選到同邊或不同邊的
: 選到同邊的話才是optimal 2*2n
: 選到不同邊的時候就變成 2*(2n-1)
: 所以最小的就會變成 2n^2 optimal:(2n)^2
: 是這樣吧?有錯請指正@@"
這題我認為是 2n*(n+1)
原PO認為是2*(n^2)應該是覺得有下列情況:
K(2n, 2n)
n n
---------
n n
但此情況的前一種情況一定是:
K(2n, 2n)
n n+1
---------
n n-1
此時 edge 數是 n*(n-1)+(n+1)*n = 2*(n^2)
edge 數沒有增加 所以應該選擇另一種情況:
K(2n, 2n)
n-1 n+1
---------
n+1 n-1
此時 edge 數是 (n-1)*(n-1)+(n+1)*(n+1) = 2*(n^2)+2
以此類推 得到的答案是 2n*(n+1)
有錯請指正!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.121.101
※ 編輯: feather585 來自: 140.113.121.101 (02/13 23:05)