想试着和大家讨论看看题目 >_< 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/cn.aspx?n=bbs/Prob_Solve/M.1421264240.A.D1E.html