POJ 3710 Christmas Game [博弈]

题意：略。

思路：这是个删边的博弈游戏。

关于删边游戏的预备知识：http://blog.csdn.net/acm_cxlove/article/details/7854532

学习完预备知识后，这一题就不难了。

首先，用tarjan算法找到每棵树中的双连通分量(即树枝上的多边形)，根据Fusion Principle，如果多边形有奇数条边，可以简化为1条边，如果有偶数条边，则可以简化为1个点。代码中使用了vis数组，对于前者，使环内所有的点（包括悬挂点）的vis值为1，后面计算sg值时便不会再进行遍历这些点；对于后者，除了悬挂点和多边形内与悬挂点相邻的一点（相邻点中只取一个）外，多边形内其他点vis为1，这样就相当于将环化为了1条边。另外，题目当中会有重边，根据题意，当出现这种情况时，一定也是出现在树枝的末端。这里直接当作多边形来处理，方法是相同的，如果有偶数条边，化为1个点，奇数条边化为1条边。

然后由Colon Principle，可以计算出整棵树的sg值，之后对于所有的树，就是个Nim游戏了。

更多细节看代码

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stack>
  4 #include<algorithm>
  5 #define maxn 105
  6 #define maxp 2000
  7 using namespace std;
  8 int map[maxn][maxn];
  9 bool vis[maxn];
 10 struct node
 11 {
 12     int v, next;
 13 }edge[maxp];
 14 int num_edge, head[maxn];
 15 void init()
 16 {
 17     num_edge = 0;
 18     memset(head, -1, sizeof(head));
 19 }
 20 void addedge(int a,int b)
 21 {
 22     edge[num_edge].v = b;
 23     edge[num_edge].next = head[a];
 24     head[a] = num_edge++;
 25 }
 26 struct scc
 27 {
 28     int dfn[maxn], low[maxn];
 29     int cnt, scnt;
 30     bool instack[maxn];
 31     stack<int> s;
 32     void init()
 33     {
 34         cnt = scnt = 0;
 35         memset(dfn, -1, sizeof(dfn));
 36         memset(instack, 0, sizeof(instack));
 37     }
 38     void tarjan(int u,int father)
 39     {
 40         dfn[u] = low[u] = ++cnt;
 41         s.push(u);
 42         instack[u] = 1;
 43         for (int i = head[u]; i != -1; i = edge[i].next)
 44         {
 45             int v = edge[i].v;
 46             if (v == father)
 47             {
 48                 if (map[u][v] > 1 && map[u][v] % 2 == 0)
 49                     vis[u] = 1;
 50                 continue;
 51             }
 52             if (dfn[v] == -1)
 53             {
 54                 tarjan(v, u);
 55                 low[u] = min(low[u], low[v]);
 56             }
 57             else if (instack[v]) low[u] = min(low[u], dfn[v]);
 58         }
 59         if (dfn[u] == low[u])
 60         {
 61             scnt = 0;
 62             int last;
 63             for (;;)
 64             {
 65                 int temv = s.top();
 66                 s.pop();
 67                 scnt++;
 68                 instack[temv] = 0;
 69                 if ((temv == u) || s.empty())
 70                     break;
 71                 vis[temv] = 1;
 72                 last = temv;
 73             }
 74             if (scnt & 1)
 75                 vis[last] = 0;
 76         }
 77         return;
 78     }
 79     void solve(int n)
 80     {
 81         init();
 82         for (int i = 1; i <= n; i++) if (dfn[i] == -1)
 83             tarjan(i, -1);
 84     }
 85 };
 86 int getsg(int u,int father)
 87 {
 88     int osum = 0;
 89     for (int i = head[u]; i != -1; i = edge[i].next)
 90     {
 91         int v = edge[i].v;
 92         if (!vis[v] && v != father)
 93             osum ^= (1 + getsg(v, u));
 94     }
 95     return osum;
 96 }
 97 int main()
 98 {
 99     int k, n, m;
100     scc g;
101     while (~scanf("%d", &n))
102     {
103         int osum = 0;
104         for (int i = 1; i <= n; i++)
105         {
106             scanf("%d%d", &m, &k);
107             int a, b;
108             init();
109             memset(map, 0, sizeof(map));
110             memset(vis, 0, sizeof(vis));
111             while (k--)
112             {
113                 scanf("%d%d", &a, &b);
114                 addedge(a, b);
115                 map[a][b]++;
116                 addedge(b, a);
117                 map[b][a]++;
118             }
119             g.solve(m);
120             osum ^= getsg(1, -1);
121         }
122         if (osum) printf("Sally
");
123         else printf("Harry
");
124     }
125     return 0;
126 }