POJ 1947 Rebuilding Roads（树形DP + 01背包）

/*01背包（最小价值） + 树形DP，做的第一道树形DP问题思路：d[i][j]：以i为跟的树，选j个节点，根必选原来一直Runtime Error，最后发现①处的问题，漏了N*/#include <cstdio>#include <cstring>const int nMax = 157;const int INF = 0x3fffffff;int next[nMax];int head[nMax];int fa[nMax];int d[nMax][nMax];int N, P;void dfs(int root){int i, j;for(i = 1; i <= P; ++ i)d[root][i] = INF;d[root][1] = 0;int p = head[root];while(p != -1){dfs(p);for(i = P; i >= 1; -- i){d[root][i] = d[root][i] + 1;for(j = 1; j < i; ++ j){if(d[root][i] > d[p][j] + d[root][i - j])d[root][i] = d[p][j] + d[root][i - j];}}p = next[p];}}int main(){while(scanf("%d%d", &N, &P) != EOF){int i;memset(head, -1, sizeof(head));memset(fa, -1, sizeof(fa));for(i = 1; i < N; ++ i){int a, b;scanf("%d%d", &a, &b);next[b] = head[a];head[a] = b;fa[b] = a;}int root;for(i = 1; i <= N; ++ i)//①{if(fa[i] == -1){root = i;break;}}dfs(root);int _min = d[root][P];for(i = 1; i <= N; ++ i){if(d[i][P] + 1 < _min)_min = d[i][P] + 1;}printf("%d\n", _min);}return 0;}