POJ1463--Strategic game Tree DP again

huangboyan · 2018-08-11 16:40:27 · 个人记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1500+10;
int a[maxn],f[maxn][maxn],fa[maxn],nt[maxn],to[maxn],head[maxn],e,p[maxn];
void add(int x,int y){
    to[++e]=y;
    nt[e]=head[x];
    head[x]=e;
}
void dfs(int x){
    p[x]=1;
    for(register int i=head[x];i;i=nt[i]){
        if(p[to[i]]==0){
            dfs(to[i]);
            f[x][0]+=f[to[i]][1];
            f[x][1]+=min(f[to[i]][0],f[to[i]][1]);
        }
    }
    return;
}
int main(){
    int i,j,k,m,n;
    while(scanf("%d",&n)!=EOF){
        e=0;
        memset(fa,-1,sizeof(fa));
        memset(f,0,sizeof(f));
        memset(p,0,sizeof(p));
        memset(to,0,sizeof(to));
        memset(nt,0,sizeof(nt));
        memset(head,0,sizeof(head));
    for(register int i=1;i<=n;i++){
        int x,y;
        scanf("%d:(%d)",&x,&y);
        for(register int j=1;j<=y;j++){
            int z;
            scanf("%d",&z);
            fa[z]=x;
            add(x,z);
        }
    }
        for(register int i=0;i<n;i++){
            if(fa[i]==-1){
                k=i;
                break;
            }
        }
        for(register int i=0;i<n;i++)f[i][1]=1;
        dfs(k);
        printf("%d\n",min(f[k][0],f[k][1]));

}
    return 0;
}