[討論] UVa12615

看板Prob_Solve作者dreamoon (大笨蛋小月唷!)時間9年前 (2015/01/15 03:37)推噓8(8推 0噓 13→)

留言21則, 4人參與討論串1/4 (看更多)

想試著和大家討論看看題目 >_< 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://www.ptt.cc/bbs/Prob_Solve/M.1421264240.A.D1E.html

推

FRAXIS

01/15 05:21, , 1^F

01/15 05:21, 1^F

推

DJWS

01/15 07:55, , 2^F

01/15 07:55, 2^F

推

DJWS

01/15 07:58, , 3^F

01/15 07:58, 3^F