组队赛的时候的一道题，那个时候想了一下感觉dp不怎么好写呀，现在写了出来，交上去过了，但是我觉得我还是应该WA的呀，因为总感觉dp的不对。
|
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
|
#pragma warning(disable:4996)#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<vector>#define maxn 150using
namespace std;
struct
Edge
{ int
v, w;
Edge(int
vi, int
wi) :v(vi), w(wi){}
Edge(){}
};vector<Edge> G[maxn];int
n, q;
int
dp[maxn][maxn];
int
tmp[maxn];
void
dfs(int
u, int
fa)
{ for
(int i = 0; i < G[u].size(); i++){
int
v = G[u][i].v, w = G[u][i].w;
if
(v == fa) continue;
dfs(v, u);
memcpy(tmp, dp[u], sizeof(dp[u]));
for
(int k = q; k >= 0; k--){
for
(int j = k - 1; j >= 0; j--){
dp[u][k] = max(dp[u][k], dp[v][j] + tmp[k-1- j] + w);
}
}
}
}int
main()
{ while
(cin >> n >> q)
{
for
(int i = 0; i <= n; i++) G[i].clear();
int
ui, vi, wi;
for
(int i = 0; i < n - 1; i++){
scanf("%d%d%d", &ui, &vi, &wi);
G[ui].push_back(Edge(vi, wi));
G[vi].push_back(Edge(ui, wi));
}
memset(dp, 0, sizeof(dp));
dfs(1, -1);
cout << dp[1][q] << endl;
}
return
0;
} |