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