UVA1292 Strategic game

跟舞会那道题差不多，如果父节点没有取那么所有子节点都必须取；如果父节点取了，子节点取或不取皆可。

$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$

需要注意的是题目中已经把子树说明了，这就意味着只能有一个点作为根节点，所以应该连单向边，并且事先找到那个点作为根节点。

struct Edge{
    int next,to;
} edge[3005];
int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505];

inline void init()
{
    cnt=0;
    memset(head,0,sizeof(head));
    memset(out,0,sizeof(out));
}

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    f[x][1]=1;
    f[x][0]=0;
    if (!head[x]) return;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        dfs(y);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][1],f[y][0]);
    }
    return;
}

int main()
{
    while (~scanf("%d",&n))
    {
        init();
        for (int i=1;i<=n;i++)
        {
            scanf("%d:(%d)",&a,&b);
            a++;
            for (int j=1;j<=b;j++)
            {
                scanf("%d",&c);
                c++;
                add(a,c);
                out[c]++;
            }
        }
        int i=1;
        while (out[i]) i++;
        dfs(i);
        printf("%d\n",min(f[i][0],f[i][1]));
    }
    return 0;
}