想試著和大家討論看看題目 >_< http://uva.onlinejudge.org/external/126/12615.html 這題是這樣的，有一個Graph,每條邊都有cost 它滿足四個條件: 1. 此圖為連通圖 2. 每個點degree至多6 3. 此圖上若有cycle，則cycle大小一定為3，且任兩個cycle沒有共用的點 4. 所有cycle上的點degree至多4 題目要你找出一個cost總和最小的邊集，滿足所有不此邊集的邊都至少與一條邊集裡的邊 相鄰，回答最小cost即可。 嗯...喜歡玩全自己想題目的可以先看到這裡...接下來我要說我目前的做法 不過我自己覺得我的方法很複雜，想問問看大家有沒有想到什麼精妙的做法 ======= 這題我的直覺就是想到在Tree上做dp 但是我設計的dp在每個點上各有9個state,每次從子節點返回時進行狀態轉移，至多有 9*9*2*2種組合，有點多且挺複雜的 首先要注意到，根據題目條件，用dfs走訪所有點後每個非root的點的back edge至多一條 ，且距離恰為2，所以每個點連出去的邊至多只會影響比它稍微靠進root的兩個祖先 接著，dp過程中，每個點我們都可用三種狀態去表示，分別是： 0:普通的點 1:尚未與任何一條邊集裡的邊相連且與至少一條不滿足條件的邊相連 2:已至少和一條邊集裡的邊相連 由於每個點連的邊至多影響兩個祖先的點，所在dp時可只記錄當前點與父節點的所有狀態 組合，共3*3種 真正的dp過程寫成psedocode會是以下這樣: dp[x][state1][state2] := 只考慮點x的子樹下所有當前已拜訪的邊和點的back edge時， 已知x點的狀態是state1,已及x點的父親的狀態是state2時的最佳解 dfs(x): dp[x][i][j] := 0 when i = j = 0 dp[x][i][j] := INF otherwise 對於所有與x相鄰且尚未拜訪過的y: dfs(y) 把tmp[3][3] 初使化為一個值全為 INF的陣列 for i1 from 0 to 2: //i1,j1,i2,j2是枚舉所有點x和y的dp狀態 for j1 from 0 to 2: for i2 from 0 to 2: for j2 from 0 to 2: for s1 from 0 to 1: //s1=1代表邊(x,y)在邊集裡 for s2 from 0 to 1://s2=1代表y有back edge且該邊在邊集 令st1,st2為根據枚舉的條件得到的x點的新的狀態(過程省略...) 若 tmp[st1][st2] > dp[x][i1][j1] + dp[y][i2][j2] + s1*(邊(x,y)的cost) + s2*(y的back edge cost): 更新tmp[st1][st2]質為右式 把tmp陣列複至給dp[x]陣列 dfs end 可以任意點r當root呼叫dfs(r),最後的答案會是min(dp[r][0][0],dp[r][2][0]) 這過程真的非常複雜，由其轉移的部分很容易就想錯... 有沒有人有更好的想法呢>_<? 此方法必須對在圖上做dfs後邊的可能位置有所了解，可以參考wiki http://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.233.216 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1421264240.A.D1E.html