最近在練樹形 DP，正好看到 這一道 虛標的紫題，但本蒟蒻不會寫，想出來了便記錄一下
題面 & 思考
先看題面，一顆有根樹，選定 k 個節點作為 ”伐木場“，求運送木料最小費用。注意木料費用是 dis * wood。
最開始想到簡單的樹形揹包，狀態轉移方程：
1
| f[i][k] = min(f[j][s] + cost, f[i][k]);
|
但是注意到，如果某個後代節點如果是伐木場，cost 不需要計算，所以狀態中還需要儲存後代的伐木場情況。
但是後代中鋸木廠不止一個。考慮到樹有唯一的父親，且同一深度祖先唯一，可以記錄最近的伐木場祖先，作為狀態的一部分。
有 f[i][j][k] 即 i 節點 最近的伐木場祖先為 j，後代（不算自己）有 k 個是伐木場。
但是由於 f 自己也可能是伐木場，轉移方程不同，需要分類討論，於是改成：f[i][j][k][0/1] 其中 0 代表自己不是伐木場， 1 表示自己是伐木場。
狀態轉移方程
因為我們需要列舉祖先，在 DFS 時需要記錄 Fa 陣列：
1
2
3
| DFS 開始時：fa[++tot] = x;
結束時：tot--;
|
簡單記錄祖先 stack。
回溯後，對於當前節點 x 和 子節點 y 每個祖先 ff：
1
2
3
4
| 先對每個 k 賦初值，對於每種伐木場個數 l：
f[x][ff][l][0] += f[y][ff][0][0]; --> 當前節點不是伐木場，子節點 y 最近伐木場為 l，對任意 f，賦最大值，即 子結點中沒有伐木場。
f[x][ff][l][1] += f[y][x][0][0]; --> 當前節點是伐木場，子節點 y 最近伐木場為 當前節點，對任意 f，賦最大值，即 子結點中沒有伐木場。
|
然後就是樹形揹包：
1
2
3
4
| f[x][ff][l][0] = min(f[x][ff][l][0], f[x][ff][l-s][0] + f[y][ff][s][0]); --> 當前節點不是伐木場，對 y 節點分配 s 個伐木場個數
f[x][ff][l][1] = min(f[x][ff][l][0], f[x][ff][l-s][1] + f[y][x][s][0]); --> 當前節點是伐木場，對 y 節點分配 s 個伐木場個數
唯一的不同是 y 節點最近祖先為 x
|
注意在列舉 l 時，由於是01揹包，需要倒過來列舉，不然狀態計算會疊加。（很容易理解）
做完了？好像還差一個 cost！
考慮到 祖先節點 ff cost 的貢獻，因為是 當前節點 W 乘以 到 ff 的總距離！
需要計算總距離，維護 dep 陣列，即當前節點到根節點距離，即可！很容易理解。ff 到 x 的距離就是 dep[x] - dep[ff]
對於當前節點 x 每一個祖先 ff：
1
2
3
4
5
6
7
8
| if(l>=1){ --> 因為 l 需要 -1 ，要分類討論。
f[x][ff][l][0] = min(f[x][ff][l][0] + W[x] * (dep[x]-dep[ff]), f[x][ff][l][1]);
合併 0 和 1，因為回溯之後，1 的狀態不再被使用，便於下一步計算。
-1 是因為上文 f[x][ff][l][1] = min(f[x][ff][l][0], f[x][ff][l-s][1] + f[y][x][s][0]); 時，s+l-s = l 但是當前節點也是伐木場，所以狀態更新是 l+1 的，要 -1 獲取正確結果
}else{
l = 0 時，當前節點不可能為伐木場，直接新增到 ff 增加的貢獻
f[x][ff][l][0] += W[x] * (dep[x]-dep[ff]);
}
|
這裡再來聊一聊合併。為了便於討論，上文揹包轉移的時候，我們沒有考慮 y 的 1 的情況，而是在每次 y 回溯時 合併 0 和 1。這有點類似於滾動陣列？回溯後 0 不再表示之前的意義，而是我們最初設計的狀態：i 節點 最近的伐木場祖先為 j，後代（或自己）有 k 個是伐木場！
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <cmath>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
struct Node {
int to, next, d;
} NDS[201];
int head[201], vis[201];
int cnt = 0;
long long W[201];
int tot = 0;
void add(int a, int b, int d) {
NDS[cnt].to = b;
NDS[cnt].next = head[a];
NDS[cnt].d = d;
head[a] = cnt++;
}
int fa[201];
long long f[201][201][52][2];
long long dep[201];
long long n, k;
void dp(int x) {
fa[++tot] = x;
vis[x] = 1;
for (int i = head[x]; i != -1; i = NDS[i].next) {
int y = NDS[i].to;
if (vis[y]) continue;
dep[y] = dep[x] + NDS[i].d;
dp(y);
for (int j = tot; j >= 1; j--) {
int ff = fa[j];
for (int l = k; l >= 0; l--) {
f[x][ff][l][0] += f[y][ff][0][0];
f[x][ff][l][1] += f[y][x][0][0];
for(int s = l; s>=0; s--){
f[x][ff][l][0] = min(f[x][ff][l][0], f[x][ff][l-s][0] + f[y][ff][s][0]);
f[x][ff][l][1] = min(f[x][ff][l][1], f[x][ff][l-s][1] + f[y][x][s][0]);
}
}
}
}
for (int j = 1; j <= tot; j++) {
int ff = fa[j];
for (int l = k; l >= 0; l--) {
if(l>=1){
f[x][ff][l][0] = min(f[x][ff][l][0] + W[x] * (dep[x]-dep[ff]), f[x][ff][l-1][1]);
}else{
f[x][ff][l][0] += W[x] * (dep[x]-dep[ff]);
}
}
}
tot--;
}
int main() {
memset(head, -1, sizeof(head));
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int w, v, d;
cin >> w >> v >> d;
W[i] = w;
add(i, v, d);
add(v, i, d);
}
dp(0);
cout << f[0][0][k][0] << endl;
return 0;
}
|
