POJ 2486 Apple Tree(树形DP + 01背包)
/*树形DP + 01背包思路：首先bfs将图转变为树，然后dfs进行动态规划。有两种状态，其中d[0][i][j]表示直通，d[1][i][j]表示返回到i节点①、②处，曾经出错临界状态的初始化，始终感觉是个难点，一直没有搞清楚。最后在测试数据1 11的时候发现问题。*/#include <cstdio>#include <cstring>const int nMax = 107;const int mMax = 207;int N, K;int A[nMax];int head[nMax], next[nMax], fa[nMax];int d[2][nMax][mMax];int map[nMax][nMax];int queue[nMax];int visit[nMax];void bfs(int root){int front, rear;front = rear = 0;queue[front ++] = root;memset(visit, 0, sizeof(visit));while(rear < front){int p = queue[rear ++];visit[p] = 1;int i;for(i = 1; i <= N; ++ i){if(map[p][i] == 1 && !visit[i]){next[i] = head[p];head[p] = i;fa[i] = p;queue[front ++] = i;}}}}void dfs(int root){int i, j;int p = head[root];for(i = 0; i <= K; ++ i)d[0][root][i] = d[1][root][i] = A[root];//②，临界状态的初始化，需要注意。//d[0][root][0] = d[1][root][0] = A[root];while(p != -1){dfs(p);int i;for(i = K; i >= 1; -- i){//d[0][root][i] = d[0][root][i];//d[1][root][i] = d[1][root][i];for(j = 0; j < i; ++ j){if(i - j - 2 >= 0 && d[1][root][i] < d[1][p][j] + d[1][root][i - j - 2])d[1][root][i] = d[1][p][j] + d[1][root][i - j - 2];if(i - j - 1 >= 0 && d[0][root][i] < d[0][p][j] + d[1][root][i - j - 1])d[0][root][i] = d[0][p][j] + d[1][root][i - j - 1];if(i - j - 2 >= 0 && d[0][root][i] < d[1][p][j] + d[0][root][i - j - 2])d[0][root][i] = d[1][p][j] + d[0][root][i - j - 2];}}p = next[p];}}int main(){//freopen("e://data.in", "r", stdin);while(scanf("%d%d", &N, &K) != EOF){int i;for(i = 1; i <= N; ++ i) scanf("%d", &A[i]);memset(fa, -1, sizeof(fa));memset(head, -1, sizeof(head));memset(map, 0, sizeof(map));for(i = 1; i < N; ++ i){int a, b;scanf("%d%d", &a, &b);//next[b] = head[a];//head[a] = b;//fa[b] = a;map[a][b] = map[b][a] = 1;//①，需要将图转变为树}bfs(1);dfs(1);/*int _max = d[0][1][K];for(i = 2; i <= N; ++ i){if(d[0][i][K] > _max)_max = d[0][i][K];}*/printf("%d\n", d[0][1][K]);}return 0;}