想試著和大家討論看看題目 >_<
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