Posted on 2008-04-24 00:22
superman 閱讀(259)
評論(0) 編輯 收藏 引用 所屬分類:
URAL
1 /* Accepted 0.001 292 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, map[101][101], opt[101][101];
7
8 struct BinaryTree
9 {
10 int num, apple;
11 BinaryTree * left, * right;
12
13 BinaryTree()
14 {
15 left = right = NULL;
16 }
17 void PostOrder()
18 {
19 if(left == NULL && right == NULL)
20 {
21 opt[num][1] = apple;
22 return;
23 }
24 if(left)
25 left -> PostOrder();
26 if(right)
27 right -> PostOrder();
28
29 for(int i = 1; i <= m; i++)
30 {
31 int max = 0;
32 for(int j = 0; j < i; j++)
33 if(max < opt[left -> num][j] + opt[right -> num][i - j - 1])
34 max = opt[left -> num][j] + opt[right -> num][i - j - 1];
35 opt[num][i] = max + apple;
36 }
37 }
38 }Tree[101];
39
40 bool visited[101];
41 void dfs(int p)
42 {
43 visited[p] = true;
44 for(int i = 1; i <= n; i++)
45 if(map[p][i] && visited[i] == false)
46 {
47 Tree[i].num = i;
48 Tree[i].apple = map[p][i];
49
50 if(Tree[p].left == NULL)
51 Tree[p].left = &Tree[i];
52 else
53 Tree[p].right = &Tree[i];
54 dfs(i);
55 }
56 }
57
58 int main()
59 {
60 cin >> n >> m; m++;
61
62 int s, t, l;
63 while(cin >> s >> t >> l)
64 map[s][t] = map[t][s] = l;
65
66 dfs(1);
67
68 Tree[1].num = 1;
69 Tree[1].apple = 0;
70 Tree[1].PostOrder();
71
72 cout << opt[1][m] << endl;
73
74 return 0;
75 }
76