hdu1054Strategic Game【树型的dp】

刚刚那个题的升级版，本来自己是套着那个的思路写的，还是字符串没处理好，转而用课件的解法了,后来搜到邝斌也是dp[i][0] dp[i][1]这么做的，发现自己的思维有漏洞dp[root][1]+=min(dp[u][0],dp[u][1]);  不是单纯的=dp[j][0]  忽略那个CE RE也算是1A了\(^o^)/~

不过这个题还是可以用最小点覆盖做==详见我的另一篇博客：弱校联萌十一大决战之强力热身D. Vertex Cover最小点覆盖【附cin加速代码】  dp比图论美丽多了==

/********
hdu1054
2015.12.27
218MS 1792K 1609 B
********/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1600
struct node
{
    int from,to,next;
}edge[N*2];
int min(int a,int b)
{
    if(a<b) return a;
    return b;
}
char str[2000];
int head[N],tol,dp[N][2],n;
bool isroot[N];
void add(int a,int b)
{
    edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;
}
void dfs(int root)
{
    dp[root][0]=0;
    dp[root][1]=1;
    for(int i=head[root];i!=-1;i=edge[i].next)
    {
        int u=edge[i].to;
        dfs(u);
        dp[root][0]+=dp[u][1];
        dp[root][1]+=min(dp[u][0],dp[u][1]);
    }
}
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        tol=0;
        memset(head,-1,sizeof(head));
        memset(isroot,false,sizeof(isroot));
        int a,b,t;
        for(int i=0;i<n;i++)
        {
            scanf("%d:(%d) ",&a,&t);
           // dp[i][0]=0;dp[i][1]=1;
           // printf("a=%d  t=%d   ",a,t);
            while(t--)
            {
                scanf("%d",&b);
                add(a,b);
                isroot[b]=true;
            }
        }
        int r;
        for(int i=0;i<n;i++)
        {
            if(!isroot[i])
            {
                dfs(i);
                //printf("root=%d   ",i);
                r=i;
                break;
            }
        }
       // for(int i=0;i<n;i++) printf("i=%d  dp[i][0]=%d dp[i][1]=%d\n",i,dp[i][0],dp[i][1]);
        printf("%d\n",min(dp[r][0],dp[r][1]));
    }
    return 0;
}