要注意数据保证了图是一棵树，树形DP。f[i]表示走到i是否必胜，如果f[j]=true (j是i的孩子) f[i]=false，否则f[i]=true。当f[start]=false时第一个恐怖分子必胜。
1 #include <iostream>
2 using namespace std;
3 int n,m;
4 int link[1001][30];
5 bool v[1001];
6 bool g[1001];
7 int q[1001],st,en;
8 bool f[1001];
9
10 void bfs(int x){
11 st=0; en=1;
12 q[1]=x;
13 v[x]=true;
14 while (st<en){
15 ++st;
16 int nx=q[st];
17 for (int i=1;i<=link[nx][0];++i) if (!v[link[nx][i]]){
18 ++en;
19 q[en]=link[nx][i];
20 v[link[nx][i]]=true;
21 }
22 }
23 }
24
25 int main(){
26 scanf("%d %d",&n,&m);
27 for (int i=1;i<n;++i){
28 int a,b;
29 scanf("%d %d",&a,&b);
30 link[a][++link[a][0]]=b;
31 link[b][++link[b][0]]=a;
32 }
33 bfs(m);
34 for (int i=n;i>0;--i){
35 int nx=q[i];
36 g[nx]=true;
37 bool re=true;
38 for (int j=1;j<=link[nx][0];++j) if (g[link[nx][j]]){
39 if (f[link[nx][j]]){
40 re=false;
41 break;
42 }
43 }
44 f[nx]=re;
45 }
46 if (!f[m]){
47 int x;
48 for (int i=1;i<=link[m][0];++i) if (f[link[m][i]]){
49 x=link[m][i];
50 break;
51 }
52 printf("First player wins flying to airport %d",x);
53 }
54 else printf("First player loses");
55 }
56
posted on 2008-11-06 17:17
Joseph 阅读(184)
评论(0) 编辑 收藏 引用