想试着和大家讨论看看题目 >_<
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