http://poj.org/problem?id=1463

 

树形dp

dp[i][0/1]表示放与不放

直接转移

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1505;
int n;
int head[N],ver[N<<1],nxt[N<<1],ce;
int f[N][2];
void dfs(int now,int lst)
{
    f[now][0]=1,f[now][1]=0;
    for(int i=head[now];i;i=nxt[i])
    {
        int y=ver[i];
        if(y==lst) continue;
        dfs(y,now);
        f[now][0]+=min(f[y][0],f[y][1]);
        f[now][1]+=f[y][0];
    }
}
int u,m;
void init()
{
    char ch[50];
    scanf("%s",ch+1);
    u=m=0;
    int i;
    for(i=1;ch[i]!=':';++i) u=u*10+ch[i]-'0';
    for(i=i+2;ch[i]!=')';++i) m=m*10+ch[i]-'0';
}
void adde(int a,int b)
{
    ver[++ce]=b,nxt[ce]=head[a],head[a]=ce;
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        for(int i=0;i<n;++i) head[i]=0;
        ce=0;
        for(int i=1;i<=n;++i)
        {
            init();
            for(int i=1;i<=m;++i)
            {
                int v;
                scanf("%d",&v);
                adde(u,v); adde(v,u);
            }
        }
        dfs(0,-1);
        printf("%d\n",min(f[0][0],f[0][1]));
    }
    
    return 0;
}