樹型DP
樹型DP
樹型DP,即在樹上做動態規劃。樹是無環圖，順序可以是從葉子到根節點，也可以從根到葉子節點。一般樹型DP的特征很明顯，即狀態可以表示為樹中的節點，每個節點的狀態可以由其子節點狀態轉移而來（從葉子到根的順序），或是由其父親節點轉移而來（從根到葉節點的順序），也可是兩者結合。找出狀態和狀態轉移方程仍然是樹型DP的關鍵。
例1：沒有上司的晚會
題目描述
Ural大學有\(N\)個職員，編號為\(1 \sim N\)。他們有從屬關系，也就是說他們的關系就像一棵以校長為根的樹，父結點就是子結點的直接上司。每個職員有一個快樂指數，第\(i\)個職員的快樂指數為\(h_i\)。 現在有個周年慶宴會，要求與會職員的快樂指數最大。但是，沒有職員愿和直接上司一起參加宴會。
數據范圍
\(1 \leq N \leq 60000, -128 \leq h_i \leq 127\)
分析
設\(f_{i,0/1}\)表示節點\(i\)不參加(或參加)晚會時子樹\(i\)的最大快樂指數。
若\(i\)不參加，則\(i\)的直接下屬\(j\)可以參加，也可以不參加。
若\(i\)參加，則\(i\)的直接下屬\(j\)不能參加宴會。
葉子節點的初始狀態\(f_{leaf,0}=0, f_{leaf, 1}=h_{leaf}\).
因為自下而上轉移，所以可以采用記憶化搜索的方法。
#include <bits/stdc++.h>
using namespace std;
#define maxn 60006
int n, ecnt, h[maxn], fir[maxn];
int f[maxn][2];
bool vis[maxn];
struct node{
intv,nxt;
}eds[maxn << 1];
void adde(int u, int v){
eds[++ecnt].v=u, eds[ecnt].nxt=fir[v], fir[v] =ecnt; //只保存父親到兒子的邊
}
int dfs(int r, bool flg){
if(f[r][flg] !=0xd0d0d0d0) returnf[r][flg];
if(flg==0) f[r][flg] =0;
elsef[r][flg] =h[r];
for(inti=fir[r]; i; i=eds[i].nxt){
intt=eds[i].v;
if(flg==0){
f[r][flg] +=max(dfs(t, 0), dfs(t, 1));
}
elsef[r][flg] +=dfs(t, 0);
}
returnf[r][flg];
}
int main(){
inta, b, root;
scanf("%d", &n);
for(inti=1; i<=n; i++)scanf("%d", &h[i]);
for(inti=1; i<n; i++){
scanf("%d%d", &a, &b);
adde(a, b);
vis[a] =1;
}
for(inti=1; i<=n; i++){
if(vis[i] ==0) {root=i; break;} //找出根節點
}
memset(f, 0xd0, sizeof f);
dfs(root, 0);
dfs(root, 1);
printf("%d\n", max(f[root][0], f[root][1]));
return0;
}
例2. 二叉蘋果樹
題目描述
有一棵蘋果樹，如果樹枝有分叉，一定是分\(2\)叉（就是說沒有只有\(1\)個兒子的結點） 這棵樹共有\(N\)個結點（葉子點或者樹枝分叉點），編號為\(1 \sim N\),樹根編號一定是\(1\)。 我們用一根樹枝兩端連接的結點的編號來描述一根樹枝的位置。下面是一顆有4個樹枝的樹:
2 5
\ /
3 4
\ /
1
現在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。 給定需要保留的樹枝數量，求出最多能留住多少蘋果。
輸入格式
第1行: \(2\)個空格分開的整數，\(N\) 和 \(Q(1 \leq Q \leq N,1 \lt N \leq 100)\)，\(N\)表示樹的結點數，\(Q\)表示要保留的樹枝數量。 接下來\(N-1\) 行描述樹枝的信息。
每行\(3\)個整數, 前兩個是它連接的結點的編號。第3 個數是這根樹枝上蘋果的數量。 每根樹枝上的蘋果不超過\(30000\)個。
輸出格式
第1行：一個整數，表示最多能留住的蘋果的數量。
分析
如果設狀態\(f_{i,j}\)為子樹\(i\)中包含\(j\)邊，轉移時不太自然。因為還要考慮節點\(i\)到兒子的邊是否保留的情況。
于是，將父子邊的邊權下放到兒子處，設狀態\(f_{i,j}\)表示子樹\(i\)包含\(j\)個點的最多蘋果數量。
于是得到狀態轉移方程為
其中\(w_i\)表示節點\(i\)的蘋果數量，\(f_{l,k},f_{r,j-1,k}\)表示左子樹,右子樹中保留指定節點的最多蘋果數，
答案為\(f_{Q+1}\)。因為包含\(Q+1\)個點時，剛好包含\(Q\)條邊。
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
bool vis[maxn];
int f[maxn][maxn], lson[maxn], rson[maxn];
int ecnt, n, m, pw[maxn], sz[maxn], fir[maxn];
struct edge{
int v, w, nxt;
}eds[maxn << 1];
void adde(int a, int b, int c){
eds[++ecnt].v = b, eds[ecnt].w = c, eds[ecnt].nxt = fir[a], fir[a] = ecnt;
eds[++ecnt].v = a, eds[ecnt].w = c, eds[ecnt].nxt = fir[b], fir[b] = ecnt;
}
void dfs(int r){
vis[r] = 1;
sz[r] = 1;
for(int i = fir[r]; i; i = eds[i].nxt){
int tv = eds[i].v;
if(!vis[tv]){
pw[tv] = eds[i].w;
if(lson[r] == 0) lson[r] = tv;
else rson[r] = tv;
dfs(tv);
sz[r] += sz[tv];
}
}
}
int dfs2(int r, int cnt){
if(f[r][cnt] >= 0) return f[r][cnt];
f[r][0] = 0;
f[r][1] = pw[r];
for(int i = max(0, cnt - 1 - sz[rson[r]]); i <= sz[lson[r]] && i < cnt; i++)
f[r][cnt] = max(f[r][cnt], dfs2(lson[r], i) + dfs2(rson[r], cnt - 1 - i) + pw[r]);
return f[r][cnt];
}
int main(){
int a, b, c;
scanf("%d %d", &n, &m);
for(int i = 1; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
adde(a, b, c);
}
dfs(1);
m++;
memset(f, -1, sizeof f);
dfs2(1, m);
printf("%d\n", f[1][m]);
return 0;
}
也可以采用樹上做背包的方式來解決，這種思路不僅能夠適用于多叉樹，代碼也很短。
參考代碼如下：
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
int f[maxn][maxn];
struct edge{
int v, w, nxt;
}eds[maxn << 1];
int n, m, ecnt, fir[maxn], sz[maxn];
bool vis[maxn];
void adde(int u, int v, int w){
eds[++ecnt].v = v, eds[ecnt].w = w, eds[ecnt].nxt = fir[u], fir[u] = ecnt;
eds[++ecnt].v = u, eds[ecnt].w = w, eds[ecnt].nxt = fir[v], fir[v] = ecnt;
}
void dfs(int r){
sz[r] = 1;
vis[r] = 1;
for(int i = fir[r]; i; i = eds[i].nxt){
int tv = eds[i].v;
if(!vis[tv]){
f[tv][0] = 0, f[tv][1] = eds[i].w;
dfs(tv);
for(int k = min(sz[r], m); k >= 1; k--)
for(int j = 0; j <= sz[tv] && j <= m - k; j++){
f[r][k + j] = max(f[r][k + j], f[r][k] + f[tv][j]);
}
sz[r] += sz[tv];
}
}
}
int main(){
int a, b, c;
scanf("%d %d", &n, &m);
m++;
for(int i = 1; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
adde(a, b, c);
}
dfs(1);
printf("%d\n", f[1][m]);
return 0;
}
例3. 戰略游戲
題目描述
Bob喜歡玩電腦游戲，特別是戰略游戲。但是他經常無法找到快速玩過游戲的辦法。現在他有個問題。
他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結點上放置最少數目的士兵，使得這些士兵能了望到所有的路。 注意，某個士兵在一個結點上時，與該結點相連的所有邊將都可以被了望到。
請你編一程序，給定一樹，幫Bob計算出他需要放置最少的士兵。
數據規模
\(n \leq 1500\)
分析
設\(f_{i,0/1}\)表示\(i\)處不放或放士兵時子樹\(i\)中的最少士兵，
轉移方程為$$f_{i,0}=\sum_{j \in i.son}f_{j,1}$$
參考代碼如下：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1600
int n, m, ecnt;
int f[maxn][2], fir[maxn];
struct edge{
int v, nxt;
}eds[maxn << 1];
void adde(int u, int v){
eds[++ecnt].v = v, eds[ecnt].nxt = fir[u], fir[u] = ecnt;
eds[++ecnt].v = u, eds[ecnt].nxt = fir[v], fir[v] = ecnt;
}
int dfs(int r, bool flg, int fa){
if(f[r][flg] >= 0) return f[r][flg];
if(flg == 0)f[r][flg] = 0;
else f[r][flg] = 1;
for(int i = fir[r]; i; i = eds[i].nxt){
int tv = eds[i].v;
if(tv != fa){
if(flg == 1) f[r][flg] += min(dfs(tv, 0, r), dfs(tv, 1, r));
else f[r][flg] += dfs(tv, 1, r);
}
}
return f[r][flg];
}
int main(){
int cnt, id, a;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %d", &id, &cnt);
id++;
for(int j = 1; j <= cnt; j++){
scanf("%d", &a);
a++;
adde(id, a);
}
}
memset(f, -1, sizeof f);
dfs(1, 0, 0);
dfs(1, 1, 0);
printf("%d\n", min(f[1][0], f[1][1]));
return 0;
}
例4.電話網絡
題目描述
Farmer John決定為他的所有奶牛都配備手機，以此鼓勵她們互相交流。
不過，為此FJ必須在奶牛們居住的\(N(1 <= N <= 10,000)\)塊草地中選一些建上
無線電通訊塔，來保證任意兩塊草地間都存在手機信號。所有的N塊草地按1..N
順次編號。
所有草地中只有\(N-1\)對是相鄰的，不過對任意兩塊草地\(A\)和\(B(1 <= A <= N;
1 <= B <= N; A != B)\)，都可以找到一個以\(A\)開頭以\(B\)結尾的草地序列，并且序列
中相鄰的編號所代表的草地相鄰。無線電通訊塔只能建在草地上，一座塔的服務
范圍為它所在的那塊草地，以及與那塊草地相鄰的所有草地。
請你幫FJ計算一下，為了建立能覆蓋到所有草地的通信系統，他最少要建
多少座無線電通訊塔。
分析
設\(f_{i,0/1,0/1}\)表示子樹\(i\)的最少的通訊塔數量，第一個\(0/1\)表示在\(i\)處不建信號塔/建信號塔，第二個\(0/1\)表示在父親處不建信號塔/建信號塔。
- \(f_{i,0,0}=min(f_{j,0,0}, f_{j,1,0})\)
如果兒子的狀態選的全是\(f_{j,0,0}\),則要將其中一個替換為\(f_{j,1,0}\),并使得增加量最小。 - \(f_{i,0,1}=min(f_{j,0,0}, f_{j,1,0})\)
- \(f_{i,1,0}=min(f_{j,0,1}, f_{j,1,1})+1\)
- \(f_{i,1,1}=min(f_{j,0,1}, f_{j,1,1})+1\)
#include <bits/stdc++.h>
using namespace std;
#define maxn 10005
#define max(a,b) (a > b ? (a) : (b))
struct edge{
int v, nxt;
}eds[maxn << 1];
int n, ecnt, fir[maxn];
int f[maxn][2][2];
void adde(int a, int b){
eds[++ecnt].v = b, eds[ecnt].nxt = fir[a], fir[a] = ecnt;
eds[++ecnt].v = a, eds[ecnt].nxt = fir[b], fir[b] = ecnt;
}
void dfs(int r, int fa){
int mindiff = 999999999;
f[r][0][0] = f[r][0][1] = 0;
f[r][1][0] = f[r][1][1] = 1;
for(int i = fir[r]; i; i = eds[i].nxt){
int tv = eds[i].v;
if(tv != fa){
dfs(tv, r);
mindiff = min(f[tv][1][0] - f[tv][0][0], mindiff);
f[r][0][0] += min(f[tv][0][0], f[tv][1][0]);
f[r][0][1] += min(f[tv][0][0], f[tv][1][0]);
f[r][1][0] += min(f[tv][0][1], f[tv][1][1]);
f[r][1][1] += min(f[tv][0][1], f[tv][1][1]);
}
}
if(mindiff > 0) f[r][0][0] += mindiff;
}
int main(){
int a, b;
scanf("%d", &n);
for(int i = 1; i < n; i++){
scanf("%d %d", &a, &b);
adde(a, b);
}
dfs(1, 0);
printf("%d\n", min(f[1][0][0], f[1][1][0]));
return 0 ;
}
例5. 樹上最遠點
題目大意
有一棵樹，有\(n\)個點，邊上有權，求每個點到其最遠點的距離。
題目范圍
$ n\leq 10^5$
分析
方法一：通過樹的直徑求
有一個性質，樹上每個點的最遠點一定是樹直徑的兩個端點之一。
這個性質可以分類討論，用反證法證明。此處略。
那么可以先求出樹的直徑，然后對直徑的兩個端點各做一次dfs，這樣，每個點都能得到兩個深度。兩個深度的最大值，即為該點到最遠點的距離。
直徑的兩個端點怎么求呢？
可以任選一個點做一次dfs，得到一個深度最大的點\(A\),然后對\(A\)再做一次dfs，得到深度最大的點\(B\). \(A, B\)即為直徑的兩個端點。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
vector<pair<int, int> > myv[maxn];
int n, dep1[maxn], dep2[maxn], dep[maxn];
int A, B, maxd;
void dfs(int r, int fa, int * dep){
for(auto p : myv[r]){
int tv = p.first, tw = p.second;
if(tv != fa){
dep[tv] = dep[r] + tw;
dfs(tv, r, dep);
}
}
}
int main(){
int a, b, c;
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i < n; i++){
cin >> a >> b >> c;
myv[a].push_back(make_pair(b, c));
myv[b].push_back(make_pair(a, c));
}
dfs(1, 0, dep);
for(int i = 1; i <= n; i++){
if(dep[i] > maxd) {
maxd = dep[i], A = i;
}
}
dfs(A, 0, dep1);
maxd = 0;
for(int i = 1; i <= n; i++){
if(dep1[i] > maxd) {
maxd = dep1[i], B = i;
}
}
dfs(B, 0, dep2);
for(int i = 1; i <= n; i++){
printf("%d\n", max(dep1[i], dep2[i]));
}
return 0;
}
方法二：采用樹型DP做
先做一次dfs，自下而上求出每個節點的子樹最長鏈和子樹次長鏈。要求最長鏈和次長鏈無重邊，即它們各屬不同的分支。
再做一次dfs，自上而下求出每個節點的全局最長鏈和全局次長鏈，這個自上而下，其實就是換根dp了。
對于節點i,
1、如果其父親的全局最長鏈未經過i,則i的全局最長鏈即為父親的全局最長鏈+1；
2、否則，i的全局最長鏈為max(父親的全局次長鏈+1，i的子樹最長鏈）
如何求點i的全局次長鏈？
1、如果父親的全局最長鏈經過i，則點i的全局次長鏈等于（節點\(i\)的子樹最長鏈，節點\(i\)的子樹次長鏈，\(i\)父親的全局次長鏈+1）的第二大的值；
2、否則，點i的全局次長鏈等于點i的子樹最長鏈
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
vector<pair<int, int> > myv[maxn];
int n;
int f[maxn][2], g[maxn][2]; //f表示子樹最遠、次遠， g表示全局最遠、次遠
void dfs1(int r, int fa){
for(auto p : myv[r]){
int tv = p.first, tw = p.second;
if(tv == fa)continue;
dfs1(tv, r);
if(f[tv][0] + tw >= f[r][0]){
f[r][1] = f[r][0];
f[r][0] = f[tv][0] + tw;
}
else if(f[tv][0] + tw >= f[r][1]){
f[r][1] = f[tv][0] + tw;
}
}
}
void dfs2(int r, int fa){
for (auto p : myv[r]){
int tv = p.first, tw = p.second;
if(tv == fa)continue;
if(g[r][0] - tw == f[tv][0]){ //全局最長鏈經過節點tv
if(g[r][1] + tw > f[tv][0]){
g[tv][1] = f[tv][0];
g[tv][0] = g[r][1] + tw;
}
else if(g[r][1] + tw > f[tv][1]){
g[tv][0] = f[tv][0];
g[tv][1] = g[r][1] + tw;
}else{
g[tv][0] = f[tv][0];
g[tv][1] = f[tv][1];
}
}
else{
g[tv][0] = g[r][0] + tw;
g[tv][1] = f[tv][0];
}
dfs2(tv, r);
}
}
int main(){
int a, b, c;
ios::sync_with_stdio(false);
while(cin >> n){
for(int i = 1; i <= n; i++) myv[i].clear();
for(int i = 1; i < n; i++){
cin >> c >> a >> b;
myv[c].push_back(make_pair(a, b));
myv[a].push_back(make_pair(c, b));
}
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
dfs1(1, 0);
g[1][0] = f[1][0], g[1][1] = f[1][1];
dfs2(1, 0);
for(int i = 1; i <= n; i++){
printf("%d\n", g[i][0]);
}
}
return 0;
}
例6. 選課
題目大意
有一個森林，共有\(n\)個節點，每個節點都有點權。你要在森林中選擇\(m\)個節點，使得點權和最大。選點時有一個條件，如果選了點\(i\),則\(i\)的父親必須選中。
數據范圍
\(n \leq 300\)
分析
方法一
zhi
分析：
方法一：多叉轉二叉
首先加上一個虛擬點，其點權為\(0\)，作為所有樹的根節點，這樣，將森林轉換為樹。
設\(f_{i,j}\)表示前子樹\(i\)中選擇\(j\)個節點的最大權值。
$f_{i,j}=\sum_{son} f_{s_k,p_k}+w_i $
其中\(s_k\)是\(i\)的兒子，\(p_k\)表示在子樹\(s_k\)中選了\(p_k\)個節點。\(\sum_{p_k}=j-1\).
轉移方程雖然列出了，但由于是多叉，枚舉\(p_k\)成了大問題。
可以多叉轉二叉來處理。
這樣就簡單多了。
其中第一種情況表示選了節點\(i\)，第二種情況表示沒有選節點\(i\),自然也不能去左子樹中選擇。
#include <bits/stdc++.h>
using namespace std;
#define maxn 305
int lson[maxn], rson[maxn], last[maxn], score[maxn], sz[maxn];
int f[maxn][maxn];
int n, m;
void dfs(int r){
sz[r] = 1;
f[r][0] = 0, f[r][1] = score[r];
if(lson[r]) dfs(lson[r]), sz[r] += sz[lson[r]];
if(rson[r]) dfs(rson[r]), sz[r] += sz[rson[r]];
if(lson[r] == 0 && rson[r] == 0)return;
else if(rson[r] == 0){ //只有左子樹
for(int i = 0; i <= sz[lson[r]] && i < m; i++) f[r][i + 1] = max(f[r][i + 1], score[r] + f[lson[r]][i]);
}
else if(lson[r] == 0){ //只有右子樹
for(int i = 0; i <= sz[rson[r]] && i <= m; i++) f[r][i] = max(f[r][i], f[rson[r]][i]); //未選r節點
for(int i = 0; i <= sz[rson[r]] && i < m; i++) f[r][i + 1] = max(f[r][i + 1], f[rson[r]][i] + score[r]); //選了r節點
}
else{ //有左右子樹
for(int i = 0; i <= sz[lson[r]] && i <= m - 1; i++){ //選了r節點
for(int j = 0; j <= sz[rson[r]] && j <= m - i - 1; j++){
f[r][i + 1 + j] = max(f[r][i + 1 + j], f[lson[r]][i] + f[rson[r]][j] + score[r]);
}
}
for(int j = 0; j <= sz[rson[r]] && j <= m; j++) f[r][j] = max(f[r][j], f[rson[r]][j]); //未選r節點
}
}
int main(){
int a, b;
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a >> b;
score[i] = b;
if(!lson[a])lson[a] = i, last[a] = i;
else{
rson[last[a]] = i;
last[a] = i;
}
}
m++;
dfs(0);
printf("%d\n", f[0][m]);
return 0;
}
方法二 背包
首先也是加一個虛擬節點，將森林變成樹。
實現有兩種方式：一種是將子樹遞歸完，再進行背包合并。
另一種是訪問到節點\(i\)時，用父親的背包加上節點\(i\)的權值去更新節點\(i\)的背包(此時父親的背包未改變)，然后遞歸完子樹\(i\)以后，再用節點\(i\)的背包去更新父親的背包。
第一種背包方式：子樹合并背包
#include <bits/stdc++.h>
using namespace std;
#define maxn 305
int n, m, ecnt, fir[maxn], f[maxn][maxn];
int sz[maxn];
int score[maxn];
struct edge{
int v, nxt;
}eds[maxn];
void adde(int a, int b){
eds[++ecnt].v = b, eds[ecnt].nxt = fir[a], fir[a] = ecnt;
}
void dfs(int r){
sz[r] = 1;
f[r][1] = score[r];
for(int i = fir[r]; i; i = eds[i].nxt){
int tv = eds[i].v;
f[tv][1] = score[r];
f[tv][0] = 0;
dfs(tv);
for(int j = m; j > 0; j--){
for(int k = 0; k <= sz[tv] && k < j; k++){
f[r][j] = max(f[r][j], f[r][j - k] + f[tv][k]);
}
}
sz[r] += sz[tv];
}
}
int main(){
int a, b;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d %d", &a, &b);
score[i] = b;
adde(a, i);
}
m++;
dfs(0);
printf("%d\n", f[0][m]);
return 0;
}
第二種背包
以dfs序，將節點\(i\)作為物品，加入背包；返回時更新父親的背包。
注意更新時，是同級更新。\(f_{r,j}\) 要被\(f_{i,j-1}\)更新，他們是同級的。
\(f_{i,j}\)隱含了它的祖先都已經選中。
#include <bits/stdc++.h>
using namespace std;
#define maxn 305
int n, m, ecnt, fir[maxn], f[maxn][maxn];
int sz[maxn];
int score[maxn];
struct edge{
int v, nxt;
}eds[maxn];
void adde(int a, int b){
eds[++ecnt].v = b, eds[ecnt].nxt = fir[a], fir[a] = ecnt;
}
void dfs(int r){
for(int i = fir[r]; i; i = eds[i].nxt){
int tv = eds[i].v;
for(int j = 0; j <= m; j++)
f[tv][j] = f[r][j] + score[tv];
dfs(tv);
for(int j = 1; j <= m; j++)
f[r][j] = max(f[r][j], f[tv][j - 1]);
}
}
int main(){
int a, b;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d %d", &a, &b);
score[i] = b;
adde(a, i);
}
m++;
memset(f, -1, sizeof f);
f[0][0] = 0;
dfs(0);
printf("%d\n", f[0][m - 1]);
return 0;
}
例7 河流
題目描述
幾乎整個Byteland王國都被森林和河流所覆蓋。小點的河匯聚到一起，形成了稍大點的河。就這樣，所有的河水都匯聚并流進了一條大河，最后這條大河流進了大海。這條大河的入海口處有一個村莊——名叫Bytetown
在Byteland國，有n個伐木的村莊，這些村莊都座落在河邊。目前在Bytetown，有一個巨大的伐木場，它處理著全國砍下的所有木料。木料被砍下后，順著河流而被運到Bytetown的伐木場。Byteland的國王決定，為了減少運輸木料的費用，再額外地建造k個伐木場。這k個伐木場將被建在其他村莊里。這些伐木場建造后，木料就不用都被送到Bytetown了，它們可以在 運輸過程中第一個碰到的新伐木場被處理。顯然，如果伐木場座落的那個村子就不用再付運送木料的費用了。它們可以直接被本村的伐木場處理。
注意：所有的河流都不會分叉，也就是說，每一個村子，順流而下都只有一條路——到bytetown。
國王的大臣計算出了每個村子每年要產多少木料，你的任務是決定在哪些村子建設伐木場能獲得最小的運費。其中運費的計算方法為：每一塊木料每千米1分錢。
編一個程序：
1．從文件讀入村子的個數，另外要建設的伐木場的數目，每年每個村子產的木料的塊數以及河流的描述。
2．計算最小的運費并輸出。
第1行：包括兩個數 \((2<=n<=100), k(1<=k<=50)\) 且 \(k<=n\)。\(n\)為村莊數，\(k\)為要建的伐木場的數目。除了bytetown外，每個村子依次被命名為\(1,2,3,\dots,n\)，bytetown被命名為\(0\)。
接下來\(n\)行，每行\(3\)個整數\(w_i(0<=wi<=10000),\)v_i(0<=vi<=n)$, \(d_i(1<=di<=10000)\), 分別表示每年\(i\)村子產的木料的塊數, 離i村子下游最近的村子(即\(i\)村子的父結點), \(i\)到父親的距離(千米)。
保證每年所有的木料流到bytetown的運費不超過\(2000,000,000\)分。
\(50\％\)的數據中\(n\)不超過\(20\)。
分析
先多叉轉二叉，然后做樹型DP.
設f[i][j][k]表示以i為根的子樹中建立j個伐木場，往祖先方向最近的伐木場在k時的最小花費。
若在i點建立伐木場，則f[i][j][k]可以轉移為：
f[i][j][k]=min(f[i.lson][p][i]+f[i.rson][j-1-p][k])
若不在i點建立伐木場，則f[i][j][k]可以轉移為：
f[i][j][k]=min(f[i.lson][p][k]+f[i.rson][j-p][k]+w[i]*(dis(i,k))
最終我們求的目標狀態為
f[r.lson][m-1][r]。
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
#define ll int
#define min(a, b) (a < b ? (a) : (b))
ll f[maxn][maxn][maxn];
int lson[maxn], rson[maxn], last[maxn];
ll d[maxn], w[maxn];
int n, k;
ll inf = 0x3f3f3f3f;
vector<pair<int, ll>> myv[maxn];
bool vis[maxn];
void dfs0(int r, int fa){
for(auto p : myv[r]){
int tv = p.first;
ll tw = p.second;
if(tv != fa){
d[tv] = d[r] + tw;
dfs0(tv, r);
}
}
}
ll dfs(int r, int cnt, int up){
if(f[r][cnt][up] != inf) return f[r][cnt][up];
if(lson[r] == 0 && rson[r] == 0)
if(cnt == 0) f[r][cnt][up] = w[r] * (d[r] - d[up]);
else f[r][cnt][up] = 0;
else if(lson[r] == 0) {
if(cnt > 0) f[r][cnt][up] = min(f[r][cnt][up], dfs(rson[r], cnt - 1, up));
f[r][cnt][up] = min(f[r][cnt][up], dfs(rson[r], cnt, up) + w[r] * (d[r] - d[up]));
}
else if(rson[r] == 0) {
if(cnt > 0) f[r][cnt][up] = min(f[r][cnt][up], dfs(lson[r], cnt - 1, r));
f[r][cnt][up] = min(f[r][cnt][up], dfs(lson[r], cnt, up) + w[r] * (d[r] - d[up]));
}
else{
for(int i = 0; i <= cnt; i++){
if(i < cnt) f[r][cnt][up] = min(f[r][cnt][up], dfs(lson[r], i, r) + dfs(rson[r], cnt - 1 - i, up));
f[r][cnt][up] = min(f[r][cnt][up], dfs(lson[r], i, up) + dfs(rson[r], cnt - i, up) + (d[r] - d[up]) * w[r]);
}
}
return f[r][cnt][up];
}
int main(){
int a;
ios::sync_with_stdio(false);
cin >> n >> k;
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; i++){
cin >> w[i] >> a >> d[i];
myv[i].push_back(make_pair(a, d[i]));
myv[a].push_back(make_pair(i, d[i]));
if(lson[a]){
rson[last[a]] = i;
last[a] = i;
}
else{
lson[a] = i;
last[a] = i;
}
}
dfs0(0, -1);
cout << dfs(lson[0], k, 0);
return 0;
}
采用子樹合并的方法也可以做。
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
#define ll long long int
int fir[maxn];
struct edge{
int v,w,nxt;
}es[maxn<<1];
int n,m,dis[maxn],sz[maxn];
int ecnt;
int fa[maxn][maxn],fadis[maxn][maxn];
int g[maxn][maxn];
int f[maxn][maxn][maxn];
int w[maxn];
void adde(int a,int b,int c){
es[++ecnt].v=b,es[ecnt].nxt=fir[a],es[ecnt].w=c,fir[a]=ecnt;
}
void dfs(int r){
for(int i=fir[r];i;i=es[i].nxt){
int tmp=es[i].v;
fa[tmp][0]=tmp;
fa[tmp][1]=r;
fadis[tmp][1]=es[i].w;
for(int j=2;fa[r][j-1];j++){
fa[tmp][j]=fa[r][j-1];
fadis[tmp][j]=fadis[r][j-1]+es[i].w;
}
dfs(tmp);
}
}
void dfs2(int r){
sz[r]=1;
f[r][1][0]=0;
if(r>1)
for(int k=1;fa[r][k];k++){
f[r][0][k]=w[r]*fadis[r][k];
}
for(int i=fir[r];i;i=es[i].nxt){
int tmp=es[i].v;
dfs2(tmp);
memset(g,0x3f,sizeof g);
for(int i=0;i<=sz[r]&&i<=m+1;i++){
for(int j=0;j<=sz[tmp]&&j<=(m+1-i);j++){
for(int k=1;fa[r][k];k++){
g[i+j][k]=min(g[i+j][k],f[r][i][k]+f[tmp][j][0]); //tmp點建了伐木場
g[i+j][k]=min(g[i+j][k],f[r][i][k]+f[tmp][j][k+1]); //tmp沒有建
}
if(i>0&&j>0)g[i+j][0]=min(g[i+j][0],f[r][i][0]+f[tmp][j][0]);
if(i>0)g[i+j][0]=min(g[i+j][0],f[r][i][0]+f[tmp][j][1]);
}
}
sz[r]+=sz[tmp];
for(int i=0;i<=sz[r];i++){
for(int j=0;fa[r][j];j++){
f[r][i][j]=g[i][j];
}
}
}
}
int main(){
int a,b;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d %d %d",&w[i+1],&a,&b);
adde(a+1,i+1,b);
}
memset(f,0x3f,sizeof f);
fa[1][0]=1;
dfs(1);
dfs2(1);
printf("%d\n",f[1][m+1][0]);
return 0;
}
浙公網安備 33010602011771號