4287585_ac_0ms_312k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define N 155
 
const int LARGE_NUMBER = 11111;

struct _node {
 _node *next;
 int id;
};
 
 _node vect[ N ];
 int n, p, root, ans, f[ N ][ N ];
 
 void initialize(int n)
 {
     for (int i = 1; i <= n; i ++)
     {
         vect[i].id = 0;
         vect[i].next = NULL;
     }
 }
 
 void insert(int v, int u)
 {
     _node *p;
     p = new _node;
     p->id = u;
     p->next = vect[v].next;
     vect[v].next = p;
     vect[v].id ++; 
 }
 
 void del(_node *p)
 {
     if (p == NULL) return ;
     del(p->next);
     delete p;
 }
 
 void init()
 {
     int s, t;
     int flag[151];
     memset(flag, false, sizeof(flag));
     for (int i = 1; i < n; i ++)
     {
         scanf("%d %d", &s, &t);
         insert(s, t);
         flag[t] = true;
     }
     t = 1;
     while (flag[t]) t ++;
     root = t;
 }

void DFS(int now)
{
    _node *q = vect[now].next;
    int tmp;
    for (int i = 0; i <= p; i ++) f[now][i] = LARGE_NUMBER;
     f[now][1] = vect[now].id; 
     q = vect[now].next;
     while (q != NULL)
     {
         DFS(q->id);
         for (int j = p-1; j >= 0; j --)
         {
             if (f[now][j] < LARGE_NUMBER)
             {
                 for (int k = 1; k < p; k ++)
                 {
                     if (f[q->id][k] < LARGE_NUMBER)
                     {
                       tmp = f[now][j] + f[q->id][k] -1;
                       if (tmp < f[now][j+k])
                       {
                           f[now][j+k] = tmp;
                       }
                     }
                 }
             }
         }
         q = q->next;;
     }
 }
 
 void dp()
 {
     DFS(root);
     
     ans = f[root][p];
     for (int i = 1; i <= n; i++)
     {
         if (f[i][p] < ans) ans = f[i][p]+1;
     }
	 printf("%d\n", ans);
 }
 
 int main()
 {
     scanf("%d %d", &n, &p);
     initialize(n);
     init();
     dp();
     return 0;
 }