Poj 1947 Rebuilding Roads Dynamic Planning 고전 제목

/*
      ：   n  ，       k      k<n           

    DP

    ：http://poj.org/problem?id=1947
  */

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

const int N=151;
const int MAX=1000000;

vector <short> tree[N];
bool hasfa[N];
short dp[N][N];
int n,p;

int min(int a,int b){
	return a<b?a:b;
}

void DFS(int root){
    for(int i=0;i<tree[root].size();i++){//          
        int so = tree[root][i];
        DFS(so); //        DFS   
        for(int j=p;j>1;j--){//            ，       ，                            
            for(int k=1;k<j;k++){//                                 //    n      k  ，                              
                dp[root][j] = min(dp[root][j],dp[root][j-k] + dp[so][k] -2);//       2      1 2   k=1,j=2 ， dp[1][2]=dp[1][1]+dp[2][1]
            }                                                             //      dp[1][1] 1-2     ，dp[2][1]     1-2   ，    
        }                                                                 //dp[1][2]   1           2          1-2                2
    }
}

int main(){
	int i;
    scanf("%d%d",&n,&p);
    memset(hasfa,0,sizeof(hasfa));
    int pa,so;
    for(i = 1;i < n;i++){
        scanf("%d%d",&pa,&so);
        tree[pa].push_back(so);
        hasfa[so]=true;
    }
    int root = 1;
    for(i=1;i<=n;i++){
		if(!hasfa[i]){
			root=i;
			break;
		}
	}
    for(i = 1;i <= n;i++){
        dp[i][1]=tree[i].size()+1;//              dp[i][1]=i       1                             
        for(int j=2;j<=n;j++)
            dp[i][j] = MAX;
    }
    DFS(root);
    dp[root][p]--;           //                                  1
    int mi = MAX;
    for(i = 1;i <= n;i++){
        mi = min(mi,dp[i][p]);//       p                     
    }
    printf("%d
",mi);
    return 0;
}