- 將城堡視為結點，道路視為邊，則是一個圖問題
- n個結點，n-1條邊，且所有結點都相連，說明該圖是一棵無根樹
- 為了方便，將該樹的根視為第1個結點，
- 玉皇大帝最后要回到根節點，等價于將T除以2，
- 在T的最大時間內獲得最大的點權值之和，即是一個樹形01背包問題，
定義d[i][j][k]為以結點i為根的子樹，考慮前j棵子樹，最大時間是k的最大價值，然后空間壓縮即可，樹形01背包可以參考洛谷P2014
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 505;
int n, T;
int a[MAXN];
unordered_map<int,int> g2[MAXN];
vector<pair<int, int>> g[MAXN];
long long d[MAXN][205] = { 0 };
void create_tree(int i) {
for (const auto& e : g2[i]) {
g2[e.first].erase(i);
create_tree(e.first);
}
}
void dfs(int i) {
d[i][0] = max(0, a[i]);
for (int j = 0; j < g[i].size(); ++j) {
int to = g[i][j].first;
int to_t = g[i][j].second;
dfs(to);
for (int t = T; t >= 0; --t) {
for (int k = 0; k + to_t <= t; ++k) {
d[i][t] = max(d[i][t], d[i][k] + d[to][t - k - to_t]);
}
}
}
}
int main() {
cin >> n >> T;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
g2[u][v] = w;
g2[v][u] = w;
}
create_tree(1);
for (int i = 1; i <= n; ++i) {
g[i] = vector<pair<int, int>>(g2[i].begin(), g2[i].end());
}
T /= 2;
dfs(1);
cout << d[1][T] << endl;
}
/*
2 1
1 1
1 2 1
2 2
1 1
1 2 1
3 0
1 1000 1000
1 2 0
3 1 0
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277408.html
標籤：其他
上一篇：一個常用的電池包電壓檢測電路