Luogu_2015 二叉苹果树

题目链接

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

Luogu_2015 二叉苹果树

 #include <queue>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, m, head[maxn], size[maxn], val[maxn], dp[maxn][maxn],ans, edge_num;

 struct Edge { int v, w, nxt; } edge[maxn << ];

 inline int read() {

   register char ch = ; register int w = , x = ;

   while( !isdigit(ch) ) w |= (ch == '-'), ch = getchar();

   while( isdigit(ch) ) x = (x * ) + (ch ^ ), ch = getchar();

   return w ? -x : x;

 }

 inline void Add_edge(int u, int v, int w) {

   edge[++edge_num].v = v, edge[edge_num].w = w;

   edge[edge_num].nxt = head[u], head[u] = edge_num;

 }

 inline int Set_value(int x, int p) {

   for(int i = head[x]; i; i = edge[i].nxt) {

     if( edge[i].v == p ) continue;

     size[x] = size[x] + Set_value(edge[i].v, x), val[edge[i].v] = edge[i].w;

   }

   return ++size[x];

 }

 inline void Deep_fs(int x, int p) {

   vector<pair<int, int> > v;

   for(int i = head[x]; i; i = edge[i].nxt) {

     if( edge[i].v == p ) continue;

     v.clear(), Deep_fs(edge[i].v, x);

     for(int j = ; j <= min(size[edge[i].v], m); ++j)

       v.push_back(make_pair(j + , dp[edge[i].v][j] + val[edge[i].v]));

     for(int j = m; j > ; --j)

       for(int k = ; k < v.size(); ++k)

         if( j >= v[k].first ) dp[x][j] = max(dp[x][j], dp[x][j - v[k].first] + v[k].second);

   }

 }

 int main(int argc, const char *argv[])

 {

   freopen("..\\nanjolno.in", "r", stdin);

   freopen("..\\nanjolno.out", "w", stdout);

   scanf("%d%d", &n, &m);

   for(int u, v, w, i = ; i < n; ++i)

     u = read(), v = read(), w = read(), Add_edge(u, v, w), Add_edge(v, u, w);

   Set_value(, ), Deep_fs(, ), printf("%d\n", dp[][m]);

   fclose(stdin), fclose(stdout);

   return ;

 }

Luogu_2014 选课

 #include <queue>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, m, head[maxn], val[maxn], siz[maxn], dp[maxn][maxn], edge_num;

 struct Edge { int v, nxt; } edge[maxn];

 inline int read() {

   register char ch = ; register int w = , x = ;

   while( !isdigit(ch) ) w |= (ch == '-'), ch = getchar();

   while( isdigit(ch) ) x = (x * ) + (ch ^ ), ch = getchar();

   return w ? -x : x;

 }

 inline void Add_edge(int u, int v) {

   edge[++edge_num].v = v;

   edge[edge_num].nxt = head[u], head[u] = edge_num;

 }

 inline int Deep_fs(int x, int p) {

   for(int i = head[x]; i; i = edge[i].nxt) {

     if( edge[i].v == p ) continue;

     siz[x] = siz[x] + Deep_fs(edge[i].v, x);

     for(int j = m; j >= ; --j)

       for(int k = ; k <= min(m, siz[edge[i].v]); ++k)

         if( j >= k +  ) dp[x][j] = max(dp[x][j], dp[x][j - k - ] + dp[edge[i].v][k] + val[edge[i].v]);

   }

   return ++siz[x];

 }

 int main(int argc, const char *argv[])

 {

   freopen("..\\nanjolno.in", "r", stdin);

   freopen("..\\nanjolno.out", "w", stdout);

   scanf("%d%d", &n, &m);

   for(int v, i = ; i <= n; ++i) v = read(), val[i] = read(), Add_edge(v, i);

   Deep_fs(, -), printf("%d\n", dp[][m]);

   fclose(stdin), fclose(stdout);

   return ;

 }

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