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

題目要求是不是要找一個maximal matching?

" target="_blank" rel="nofollow">
" target="_blank" rel="nofollow">
觀眾可能比較多看起來是 edge dominating setmaximal matching 是 edge indepenent setindependent

ICPC台灣參賽者交流社根本沒人在討論題目...資訊競賽選手新手村到是第一次看到若把邊當點，大概可以應轉成一般圖的最大獨立集而且每條邊至多和六條邊相鄰這樣才真的有用到題目條件新手村的成員都太年輕了0.0

你的作法是不是tree decomposition?這個圖的tree width看起來好像只有2..

若把邊當點，是最小支配集。它不等於最大獨立集。

抱歉說錯名詞查了一下什麼是tree decomposition,看來我的做法確實是這個東西一般圖最小支配集能做嘛?

minimum dominating set是NPC..

感覺上在這個圖的BFS Tree作DP會不會比較簡單?呃 不會 當我沒說 =口=