一道有向图博弈

题目链接：http://codeforces.com/contest/787/problem/C
简介: 如果状态图是一棵有向树的话，博弈很简单，就不讲了。但如果是个图的话就非常麻烦，会存在环，会存在平局
比如下面两图：

1.PNG 2.PNG

题解: 综上类似于记忆化搜索或者是由未知找已知的方法是不可取的。合适的方法为由已知推逆推出未知，但我们知道比败态的条件为他的后继状态都是必胜态， 当我们发现一个必胜态是不能确定也不能假定它的前继状态为必败态。
比如图3：

pic3.PNG

新学的一个办法是记录下它的出度，当他的后继状态为必胜态时度数-1， 后继状态为必败态时，他为必胜态。度数减到0了他为必败态。

代码根据他人AC的代码修改得来，增加可读性

#include<cstdio>
#define Win 1
#define Lose 2
const int MAXN = 1<<13;
int n, f[2][MAXN];
int sz[2], s[2][MAXN];
int degree[2][MAXN];
void update(int x, int pos, int v) {
    if(f[x][pos]) return;
    if(pos==0) v=Lose;
      /*本来题目定义0没有后继状态的，
        但很可能会有必败态结点倒推出0，并使0成为必胜态！！
        这道题源有2个，如果源有1个，或者用bfs就不虚
      */
    f[x][pos] = v;
    if(v==Lose) {
        for(int i=0; i<sz[!x]; ++i)
            update(!x, (pos-s[!x][i]+n)%n, Win);
    }
    else if(v==Win) {
        for(int i=0; i<sz[!x]; ++i) {
            int npos = (pos-s[!x][i]+n)%n;
            --degree[!x][npos];
            if(!degree[!x][npos]) 
                update(!x, npos, Lose);
        }
    }
}
int main() {
    scanf("%d", &n);
    for(int i=0; i<2; ++i) {
        scanf("%d", sz+i);
        for(int j=0; j<sz[i]; ++j)
            scanf("%d", s[i]+j);
        for(int j=1; j<n; ++j)
            degree[i][j] = sz[i];
    }
    update(0,0,Lose);
    update(1,0,Lose);
    for(int i=0; i<2; ++i)
        for(int j=1; j<n; ++j) {
            if(f[i][j]==Lose) printf("Lose");
            else if(f[i][j]==Win) printf("Win");
            else printf("Loop");
            if(j==n-1) putchar('\n');
            else putchar(' ');
        }
    return 0;
}