treedp:
#include<iostream>
using namespace std;
int N,k;
int chd[2100],pre[2100],now[1100];
bool f[1010];
bool vis[1010];
int ans;
void treedp(int x){
vis[x]=1;
while(now[x]>0){
if(!vis[chd[now[x]]]){
treedp(chd[now[x]]);
if(!f[chd[now[x]]]){
f[x]=1;
if(x==k){
if(ans>chd[now[x]])
ans=chd[now[x]];
}
else return;
}
}
now[x]=pre[now[x]];
}
}
int main()
{
scanf("%d%d",&N,&k);
int c=0,x,y;
memset(now,0,sizeof(now));
for(int i=1;i<N;++i){
scanf("%d%d",&x,&y);
c++; pre[c]=now[x]; chd[c]=y; now[x]=c;
c++; pre[c]=now[y]; chd[c]=x; now[y]=c;
}
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
ans=0xFFFFFFF;
treedp(k);
if(!f[k]) printf("First player loses\n");
else printf("First player wins flying to airport %d\n",ans);
return 0;
}
非递归：
#include<iostream>
using namespace std;
struct arr{
int win,used;
}f[1001];
int N,k;
int g[1001][1001]={0};
int dis[1001]={0};
int deg[1001]={0};
void input()
{
scanf("%d%d",&N,&k);
int x,y;
for(int i=1;i<N;++i){
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=1;
deg[x]++; deg[y]++;
}
for(int i=1;i<=N;++i)
if(deg[i]==1&&i!=k){
f[i].used=1; f[i].win=0;
}
else f[i].used=f[i].win=0;
}
void bfs(){
int que[10001],h,t;
int vis[1001]={0};
h=t=1;
que[1]=k; vis[k]=1;
while(h<=t){
int x=que[h];
for(int y=1;y<=N;++y)
if(g[x][y]&&!vis[y]){
t++;
que[t]=y;
vis[y]=1;
dis[y]=dis[x]+1;
}
h++;
}
}
void dp()
{
int link[1001]={0};
int cur[10001]={0};
int top=1;
int ret=-1;
link[1]=k;
do{
if(ret==0)
f[link[top]].win=1;
cur[top]++;
while((g[link[top]][cur[top]]==0||dis[cur[top]]!=dis[link[top]]+1)&&cur[top]<=N)
cur[top]++;
if(cur[top]>N||f[link[top]].used==1){
f[link[top]].used=1;
ret=f[link[top]].win;
cur[top]=0;
--top;
}
else{
++top;
ret=-1;
link[top]=cur[top-1];
}
}while(top);
}
int main()
{
freopen("funnyg.in","r",stdin);
freopen("funnyg.out","w",stdout);
input();
bfs();
dp();
if(f[k].win==0)
printf("First player loses\n");
else{
for(int i=1;i<=N;++i)
if(dis[i]==1&&f[i].win==0){
printf("First player wins flying to airport %d\n",i);
break;
}
}
return 0;
}
posted on 2009-05-30 19:51
xfstart07 阅读(184)
评论(0) 编辑 收藏 引用 所属分类:
代码库