有一棵有n个顶点的树。我们被要求计算多重集 S 的最小大小,例如树中的每条边 (u,v) 至少满足以下条件之一:
- u ∈ S
- v∈S
- S中至少有两个顶点,每个顶点都与u或v相邻。
由于 S 是一个多重集,一个顶点可能多次出现在 S 中。
我的直觉如下。首先,我们考虑以下事实:在最优解中,每个顶点至多在 S 中两次。所以我们可以后序遍历树,计算顶点不在最优S、一次在一次和两次在三种情况下的结果。
不幸的是,我无法链接子问题之间的关系,我不确定这个想法是否正确。
欢迎提供提示或引用。非常感谢。
最佳答案
像这样表示树(未经测试的 Haskell)。
> data Tree a = Node a
> | Cons (Tree a) (Tree a)
树
1
/|\
2 3 4
|
5
是
(Cons (Node 2)
(Cons (Cons (Node 5) (Node 3))
(Cons (Node 4) (Node 1)))) :: Tree Int .
这是一个自下而上的验证函数。
> type ZeroOneOrTwo = Int
> data Result = Failure
> | Success { numDist0Provided :: ZeroOneOrTwo
> , numDist1Provided :: ZeroOneOrTwo
> , numDist1Required :: ZeroOneOrTwo
> }
>
> plus, minus :: ZeroOneOrTwo -> ZeroOneOrTwo -> ZeroOneOrTwo
> x `plus` y = min 2 (x + y)
> x `minus` y = max 0 (x - y)
>
> evaluate :: Tree ZeroOneOrTwo -> Bool
> evaluate t = case evaluate' t of
> Failure -> False
> s -> 0 == numDist1Required s
>
> evaluate' :: Tree ZeroOneOrTwo -> Result
> evaluate' (Node x) = Success { numDist0Provided = x
> , numDist1Provided = 0
> , numDist1Required = 0
> }
> evaluate' (Cons t1 t2) = case (evaluate' t1, evaluate' t2) of
> (Failure, _) -> Failure
> (_, Failure) -> Failure
> (s1, s2) ->
> if numDist0Provided s2 < numDist1Required s1 then Failure
> else Success { numDist0Provided = numDist0Provided s2
> , numDist1Provided = numDist1Provided s2 `plus` numDist0Provided s1
> , numDist1Required = max (numDist1Required s2 `minus` numDist0Provided s1)
> (if 0 < numDist0Provided s1 || 0 < numDist0Provided s2 then 0
> else 2 `minus` (numDist1Provided s1 `plus` numDist1Provided s2))
> }
我将把相应的线性时间 DP 作为练习。
关于algorithm - 一个有趣的图形任务,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33710792/