HDU-1054 Strategic Game(树形DP)

Strategic Game

Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 17 Accepted Submission(s) : 11 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

The input file contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes the description of each node in the following format node_identifier:(number_of_roads) node_identifier1 node_identifier2 … node_identifier or node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.

For example for the tree:

the solution is one soldier ( at the node 1).

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table: Sample Input 4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0) Sample Output 1 2

经典简单直白的树形DP题目， 这是我写的第一道树形dp题目，其实树形DP问题，从这道题目就可以找到其中的规律，树形DP无非是在树上面进行动态规划。这道题目是在DFS遍历的过程，进行动态规划，状态转移方程是： dp[root][0]+=dp[k][1]; dp[root][1]+=min(dp[root][0],dp[root][1]); 状态转移方程不难理解，结合题目的意思就可以得到。 这里dfs配合状态转移方程，前面也写到过，其实dfs就是遍历所有情况，一般的动态规划，都是遍历到所有的情况才得出来最优解。dfs就像一般DP里的几层for循环。注意，状态转移方程的位置， 还有一道题目和这个题目是差不多，建议一起做一下 http://acm.hdu.edu.cn/showproblem.php?pid=1520 做完之后总计一下，对树形DP就应该初步的了解

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdlib.h>

using namespace std;
#define MAX 1500
int n;
int root;
int tot;
struct Node
{
    int value;
    int next;
}edge[MAX*2+5];
int head[MAX+5];
int dp[MAX+5][2];
int vis[MAX+5];
void add(int x,int y)
{
    edge[tot].value=y;
    edge[tot].next=head[x];
    head[x]=tot++;
}
void dfs(int root)
{
    dp[root][0]=0;
    dp[root][1]=1;
    vis[root]=1;
    for(int i=head[root];i!=-1;i=edge[i].next)
    {
        int k=edge[i].value;
        if(!vis[k])
        {
            dfs(k);
            dp[root][0]+=dp[k][1];
            dp[root][1]+=min(dp[k][0],dp[k][1]);

        }
    }
}
int main()
{

    int a,b;
    int m;
    while(scanf("%d",&n)!=EOF)
    {
        tot=0;
        memset(vis,0,sizeof(vis));
        memset(head,-1,sizeof(head));
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d:(%d)",&a,&m);
            if(i==0) root=a;
            for(int j=0;j<m;j++)
            {
                scanf("%d",&b);
                add(a,b);
                add(b,a);
            }
        }
        dfs(root);
        printf("%d\n",min(dp[root][0],dp[root][1]));


    }
    return 0;
}