d*******i
发帖数: 117 | 1 "
Suppose we are given a rooted tree T with n leaves and m non-leaf nodes.
Each leaf is colored with one of k < n given colors, so several leaves can
have the same color. We need to color each interior node of T with one of
the k given colors to maximize the number of edges whose (two) endpoints
are colored the same color.
We can solve this with a DP algorithm that runs in O(mk) time. Let V (v,
i) denote the optimal solution value when the problem is applied to the
subtree rooted at node v, and v is required to be given color i. Let V (v)
denote the optimal solution value when the problem is applied to the
subtree rooted at node v, and there is no restriction on which of the k
colors v can be.
a. Using that notation, develop recurrences for this problem, and explain
the correctness of your recurrences.
b. Explain how the recurrences are evaluated (solved) in an efficient DP
way.
c. Show that the time bound for your DP is O(mk).
“ | m**q
发帖数: 189 | 2 设f(v, i)表示节点v的parent节点设为x颜色时，以v为根的子树中
拥有的两个端点同色的边的个数（包括v和v的parent之间的边）
则：所求为min {f(root, i)} (1<= i <= k)
f(v, i) = sum{f(c,i)} (v is root, c is child of v)
min ( 1 + sum {f(c, i)}, { min (sum {f(c, j)}), j!= i })
(v is non leaf, c is child of v)
1 (v is leaf && color(v) == i)
0 (v is leaf && color(v) != i)
Note here v is a pointer, you can create a hash table with v as key
and each v is associated with an int identifier, so we can use an
array like f[x, i] (1<= x <=m, 1<= i <=k). Complexity is O(km)
nodes.
can
of
endpoints
(v,
the
(v)
【在 d*******i 的大作中提到】
: "
: Suppose we are given a rooted tree T with n leaves and m non-leaf nodes.
: Each leaf is colored with one of k < n given colors, so several leaves can
: have the same color. We need to color each interior node of T with one of
: the k given colors to maximize the number of edges whose (two) endpoints
: are colored the same color.
: We can solve this with a DP algorithm that runs in O(mk) time. Let V (v,
: i) denote the optimal solution value when the problem is applied to the
: subtree rooted at node v, and v is required to be given color i. Let V (v)
: denote the optimal solution value when the problem is applied to the
|
|
