Luogu_2015 二叉苹果树

题目链接

SB 裸题……就是想随便挂在这里……同样的题还有 Luogu_2014 选课。

Luogu_2015 二叉苹果树

 1 #include <queue>
 2 #include <cstdio>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 const int maxn = 100 + 10;
10 int n, m, head[maxn], size[maxn], val[maxn], dp[maxn][maxn],ans, edge_num;
11 
12 struct Edge { int v, w, nxt; } edge[maxn << 1];
13 
14 inline int read() {
15   register char ch = 0; register int w = 0, x = 0;
16   while( !isdigit(ch) ) w |= (ch == '-'), ch = getchar();
17   while( isdigit(ch) ) x = (x * 10) + (ch ^ 48), ch = getchar();
18   return w ? -x : x;
19 }
20 
21 inline void Add_edge(int u, int v, int w) {
22   edge[++edge_num].v = v, edge[edge_num].w = w;
23   edge[edge_num].nxt = head[u], head[u] = edge_num;
24 }
25 
26 inline int Set_value(int x, int p) {
27   for(int i = head[x]; i; i = edge[i].nxt) {
28     if( edge[i].v == p ) continue;
29     size[x] = size[x] + Set_value(edge[i].v, x), val[edge[i].v] = edge[i].w;
30   }
31   return ++size[x];
32 }
33 
34 inline void Deep_fs(int x, int p) {
35   vector<pair<int, int> > v;
36   for(int i = head[x]; i; i = edge[i].nxt) {
37     if( edge[i].v == p ) continue;
38     v.clear(), Deep_fs(edge[i].v, x);
39     for(int j = 0; j <= min(size[edge[i].v], m); ++j)
40       v.push_back(make_pair(j + 1, dp[edge[i].v][j] + val[edge[i].v]));
41     for(int j = m; j > 0; --j)
42       for(int k = 0; k < v.size(); ++k)
43         if( j >= v[k].first ) dp[x][j] = max(dp[x][j], dp[x][j - v[k].first] + v[k].second);
44   }
45 }
46 
47 int main(int argc, const char *argv[])
48 {
49   freopen("..\nanjolno.in", "r", stdin);
50   freopen("..\nanjolno.out", "w", stdout);
51 
52   scanf("%d%d", &n, &m);
53   for(int u, v, w, i = 1; i < n; ++i)
54     u = read(), v = read(), w = read(), Add_edge(u, v, w), Add_edge(v, u, w);
55   Set_value(1, 0), Deep_fs(1, 0), printf("%d
", dp[1][m]);
56 
57   fclose(stdin), fclose(stdout);
58   return 0;
59 }

Luogu_2014 选课

 1 #include <queue>
 2 #include <cstdio>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 const int maxn = 300 + 10;
10 int n, m, head[maxn], val[maxn], siz[maxn], dp[maxn][maxn], edge_num;
11 
12 struct Edge { int v, nxt; } edge[maxn];
13 
14 inline int read() {
15   register char ch = 0; register int w = 0, x = 0;
16   while( !isdigit(ch) ) w |= (ch == '-'), ch = getchar();
17   while( isdigit(ch) ) x = (x * 10) + (ch ^ 48), ch = getchar();
18   return w ? -x : x;
19 }
20 
21 inline void Add_edge(int u, int v) {
22   edge[++edge_num].v = v;
23   edge[edge_num].nxt = head[u], head[u] = edge_num;
24 }
25 
26 inline int Deep_fs(int x, int p) {
27   for(int i = head[x]; i; i = edge[i].nxt) {
28     if( edge[i].v == p ) continue;
29     siz[x] = siz[x] + Deep_fs(edge[i].v, x);
30     for(int j = m; j >= 0; --j)
31       for(int k = 0; k <= min(m, siz[edge[i].v]); ++k)
32         if( j >= k + 1 ) dp[x][j] = max(dp[x][j], dp[x][j - k - 1] + dp[edge[i].v][k] + val[edge[i].v]);
33   }
34   return ++siz[x];
35 }
36 
37 int main(int argc, const char *argv[])
38 {
39   freopen("..\nanjolno.in", "r", stdin);
40   freopen("..\nanjolno.out", "w", stdout);
41 
42   scanf("%d%d", &n, &m);
43   for(int v, i = 1; i <= n; ++i) v = read(), val[i] = read(), Add_edge(v, i);
44   Deep_fs(0, -1), printf("%d
", dp[0][m]);
45 
46   fclose(stdin), fclose(stdout);
47   return 0;
48 }

　—— 假如我今生无份遇到你，就让我永远感到恨不相逢 —— 让我念念不忘，让我在醒时梦中都怀带着这悲哀的苦痛。