题解 P2016 【战略游戏】

jiangminghong · 2018-08-07 15:02:37 · 题解

f(x) 表示选定 x, 保证子树合法，子树内所需要的最小点数。

g(x) 表示不选择 x, 保证子树合法所需要的最小点数

f(x) = ∑min{f(son[x]), g(son[x])}

g(x) = ∑f(son[x])

#include<stdio.h>
#define inf 1000000000
int n,a,b,c,idx,head[1501],f[1501][2];
struct Edge
{
    int to,next;
}edge[3001];
int min(int x,int y)
{
    if(x<y)
        return x;
    return y;
}
void addedge(int x,int y)
{
    ++idx;
    edge[idx].to=y;
    edge[idx].next=head[x];
    head[x]=idx;
}
void dfs(int x,int from)
{
    f[x][1]=1;
    f[x][0]=0;
    if(head[x]==0) f[x][0]=inf;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(edge[i].to!=from)
        {
            dfs(edge[i].to,x);
            f[x][1]+=min(f[edge[i].to][1],f[edge[i].to][0]);
            f[x][0]+=f[edge[i].to][1];
        }
    }   
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);a++;
        for(int j=1;j<=b;j++)
        {
            scanf("%d",&c);c++;
            addedge(a,c);
            addedge(c,a);
        }
    }
    dfs(1,0);
    printf("%d",min(f[1][1],f[1][0]));
}