poj1463——Strategic game

44424742

注意一点：用链表存储树。
差点就悲剧了 限时2000ms 我的程序跑了1700+ 险！
#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define maxn 1505 bool vis[maxn],son[maxn];int min(int a,int b){return a<b?a:b;}int n;int dproot[maxn],all[maxn];int head[maxn],len;class node{public:int v,next;};void solve(int root,node g[]){int i,minnode=0;vis[root]=false;if(son[root]){dproot[root]=1;all[root]=0;return ;}for(i=head[root];i;i=g[i].next ){int v=g[i].v ;if(vis[v])     solve(v,g);    dproot[root]+=all[v];minnode+=dproot[v];}dproot[root]+=1;all[root]=min(dproot[root],minnode);}void create(int root,int temp,node  g[]){g[++len].v=temp;g[len].next=head[root];head[root]=len;}int main(){int i,k,j,root,temp;char a,b,c;while(scanf("%d",&n)!=EOF){node g[maxn*3];len=0;memset(head,0,sizeof(head));memset(vis,true,sizeof(vis));memset(son,true,sizeof(son));memset(dproot,0,sizeof(dproot));memset(all,0,sizeof(all));for(i=1;i<=n;i++){cin>>root>>a>>b>>k>>c;for(j=0;j<k;j++){cin>>temp;vis[temp]=false;create(root,temp,g);son[root]=false;}}for(i=0;i<n;i++)if(vis[i]) {temp=i;break;}memset(vis,true,sizeof(vis));solve(temp,g);printf("%d\n",all[temp]);}return 0;}