算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   给一个(N<10,000)的有向无环图,有M个物体坐落在若干个点上。A和B每次可以将某物体沿着某条边移动一次。多个物体可以重合。不能移动者算输。
算法分析:
   SG定理,可以先拓扑排序然后再SG。
 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<bitset>
 5 using namespace std;
 6 int n,m;
 7 const int N = 10005;
 8 const int M = 100005;
 9 int head[N],nxt[M],pnt[M],e,dp[N];
10 inline void add(int u,int v){
11     nxt[e] = head[u]; head[u] = e; pnt[e++] = v;
12 }
13 struct node{int id,pre;} tmp[N];
14 int tim,vis[N];
15 void dfs(int u){
16     vis[u] =1;
17     for(int i = head[u]; i!= -1; i=nxt[i]){
18         if(!vis[pnt[i]]) dfs(pnt[i]);
19     }
20     tmp[u].id = u;
21     tmp[u].pre=tim++;
22 }
23 bool cmp(node a,node b){return a.pre < b.pre;}
24 void process(){
25     tim =0;
26     for(int i = 1; i <= n; i++) vis[i] = 0;
27     for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i);
28     sort(tmp+1,tmp+n+1,cmp);
29     bitset<2*N> mp;
30     for(int p = 1; p <= n; p++) {
31         int u = tmp[p].id;
32         mp.reset();
33         for(int i = head[u]; i!=-1; i=nxt[i]){
34             int v = pnt[i];
35             mp[dp[v]] = 1;
36         }
37         for(int i = 0; i < mp.size(); i++) if(!mp[i]){
38             dp[u] = i;
39             break;
40         }
41     }
42 }
43 int main(){
44     int ctest = 1;
45     while(scanf("%d",&n)!=EOF){
46         for(int i = 1; i <= n; i++) head[i] = -1;
47         e = 0;
48         for(int i = 1; i < n; i++ ){
49             int t,v;
50             scanf("%d",&t);
51             while(t--){
52                 scanf("%d",&v);
53                 add(i,v);
54             }
55         }
56         process();
57         int t; scanf("%d",&t);
58         printf("Case %d:\n",ctest++);
59         while(t--){
60             int val = 0,c,v;
61             scanf("%d",&c);
62             while(c--) {
63                 scanf("%d",&v);
64                 val ^= dp[v];
65             }
66             puts(val?"Alice":"Bob");
67         }
68     }
69 }
70 
posted on 2012-12-23 14:04 西月弦 阅读(415) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理