首页 > 代码库 > POJ1463 Strategic game

POJ1463 Strategic game

题解:

树形dp,最小独立集裸题

代码:

#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 2097152typedef pair<int,int> P;const double eps=1e-9;const int maxn=1510;const int mod=1e9+7;int dp[maxn][2],not_root[maxn];vector<int> Edge[maxn];int n,root,num;int DP(int u,int j){    int& ans=dp[u][j];    if(ans>=0) return ans;    ans=0;    if(j) ans+=1;    for(int i=0;i<Edge[u].size();i++){        if(j) ans+=min(DP(Edge[u][i],0),DP(Edge[u][i],1));        else  ans+=DP(Edge[u][i],1);    }    return ans;}int main(){    while(~scanf("%d",&n)){        memset(not_root,0,sizeof(not_root));        memset(dp,-1,sizeof(dp));        for(int i=0;i<n;i++) Edge[i].clear();        for(int i=1;i<=n;i++){            int u,num,v;            scanf("%d:(%d)",&u,&num);            for(int i=1;i<=num;i++){                scanf("%d",&v);                Edge[u].pb(v);                not_root[v]=1;            }            for(int i=0;i<n;i++){                if(!not_root[i]){                    root=i;                    break;                }            }        }        num=DP(root,0);        memset(dp,-1,sizeof(dp));        num=min(num,DP(root,1));        printf("%d\n",num);    }    return 0;}

 

POJ1463 Strategic game