題目描述：
給一個(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
西月弦 閱讀(428)
評論(0) 編輯 收藏 引用