#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2000; int first[maxn],tot; int dp[maxn][3]; int n,in[maxn]; struct Edge { int from,to,next; }E[maxn]; void init() { memset(first,-1,sizeof(first)); tot=0; memset(dp,-1,sizeof(dp)); memset(in,0,sizeof(in)); } void addedge(int u,int v) { E[tot].from=u; E[tot].to=v; E[tot].next=first[u]; first[u]=tot++; } int dfs(int u,bool flag) { if(flag){ if(dp[u][1]!=-1) return dp[u][1];} else { if(dp[u][0]!=-1) return dp[u][0];} dp[u][1]=1; dp[u][0]=0; for(int e=first[u];e!=-1;e=E[e].next) { int v=E[e].to; dp[u][1]+=min(dfs(v,true),dfs(v,false)); dp[u][0]+=dfs(v,true); } if(flag) return dp[u][1]; return dp[u][0]; } int main() { while(scanf("%d",&n)!=EOF) { init(); int node,num,a; for(int i=0; i<n; i++) { scanf("%d:(%d)",&node,&num); for(int i=0; i<num; i++) { scanf("%d",&a); in[a]++; addedge(node,a); } } int root; for(int i=0;i<n;i++) if(in[i]==0){root=i;break;} // cout<<"root "<<root<<endl; printf("%d\n",min(dfs(root,true),dfs(root,false))); // for(int i=0;i<n;i++) // cout<<dp[i][0]<<" "<<dp[i][1]<<endl; } }
原文:http://www.cnblogs.com/Airplus/p/3869066.html