CF GYM 100548 The Problem to Make You Happy（2014ACM西安现场赛Problem H）

ProblemH. The Problem to Make You Happy

Description

Alice and Bob aregood friends, as in every other storyline. One day Alice and Bob areplaying an interesting game. The game is played on a directedgraph with n vertices and m edges, Alice and Bob have exactly onechess piece each. Initially, Bob’s chess piece is placed on vertexx, while Alice’s chess piece is placed at vertex y. Bob playsfirst, then Alice, then Bob, then Alice and so on.

During each move,the player must move his/her chess piece from the vertex his/herchess piece currently at to an adjacent vertex, by traveling throughexactly one directed edge. (Remember that the game is played on adirected graph.) If someone can’t make such a move, he/shewill be considered to lose the game.

There’s oneadditional rule: at any time, if Bob and Alice’s chess pieces areat the same vertex, then Alice is consider to be the winner and thegame ends up immediately.

Now you are giventhe initial situation, could you determine who is the winner? Pleasenote that neither Bob nor Alice will make any mistakes during thegame, i.e. they both play optimally. In case that the game never endsup, Bob is considered to be the winner.

Input

The first line ofthe input gives the number of test cases, T. T test cases follow.

For each test case,the first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤m ≤ n × (n ? 1)). Next m lines, each line contains two integersb and e, indicating there is one directed edge from vertex b tovertex e. Last line contains two integers x and y (1 ≤ x, y ≤ n, x = ?y), which are Bob and Alice’s initial position. The graphcontains no self-loops or duplicate edges.

Output

For each test caseoutput one line “Case #x: y”, where x is the case number(starting from 1) and y is “Yes” (without quotes) if Bob can winor the game never ends up, otherwise “No” (without quotes).

Samples

知识点：

有向图，博弈论，动态规划。

题目大意：

Alice和Bob两人玩游戏。两人各有一个棋子，开始时在有向图中不同的点上。Bob先手，两人轮流移动棋子，每次只能将棋子移到相邻的点上（沿着图上的有向边），不断重复这样的过程，当那人无法移动时，他就输了（规则1）。

还有两条附加规则：任何时候，当两个棋子到达同一点时，Alice胜出（规则2）。如果游戏永远无法结束，Bob胜出（规则3）。

两人都遵循最优策略，轮流移动棋子，问最终谁会赢。图中没有自环和重边。

解题思路：

根据博弈论的性质，一个局面是必胜态的充要条件是该局面进行某种决策后会成为必败态；一个局面是必败态的充要条件是该局面无论进行何种决策均会成为必胜态。

可以用动态规划解题。

dp[i][j][who]表示，当前轮到who（Alice/Bob）移动棋子，而此时Alice的棋子在i点，Bob的棋子在j点，这种状态是不是必胜态。

当i与j相同时，若who为Alice，则当前状态是必胜态，否则是必败态。（规则2）

因为图中可能出现环，使得游戏无法终止，所以还需记录状态是否访问过，如果当前状态访问过，但在递归其子状态后还没有得出这一状态的结论，却又再次访问了这一状态，就说明有环存在，应该判定Bob胜出，游戏终止。即在这种情况下，若who为Bob，则是必胜态，否则是必败态。（规则3）

如果当前状态没有子状态，那么当前状态就是必败态。（规则1）

其他情况下，就按照博弈论的性质推。如果当前状态的所有子状态都是必胜态，那么当前状态就是必败态；如果当前状态的所有子状态中存在必败态，那么当前状态就是必胜态。

最后，如果起始状态dp[x][y][Bob]是必胜态，则说明Bob赢，否则Alice赢。

参考代码：（未AC）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 110;
int nCase, cCase, n, m, x, y, dp[MAXN][MAXN][2];  // dp[x][y][who] : -1 - initial, 0 - lose state, 1 - win state
vector<int> G[MAXN];
bool visited[MAXN][MAXN][2];

void init() {
    for (int i = 0; i < MAXN; i++) {
        G[i].clear();
    }
    memset(dp, -1, sizeof(dp));
    memset(visited, false, sizeof(visited));
}

void input() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int b, e;
        scanf("%d%d", &b, &e);
        G[b].push_back(e);
    }
    scanf("%d%d", &x, &y);
}

int DP(int x, int y, int who) {  // who: 0-Bob, 1-Alice
    if (dp[x][y][who] != -1) return dp[x][y][who];
    if (x == y) return who == 1 ? 1 : 0;

    if (visited[x][y][who]) return who == 0 ? 1 : 0;
    visited[x][y][who] = true;

    if (who == 0) {  // Bob
        int flag = 0;
        for (int i = 0; i < G[x].size(); i++) {
            if (DP(G[x][i], y, 1) == 0) {
                flag = 1;
                break;
            }
        }
        dp[x][y][who] = flag;
    } else if (who == 1) {  // Alice
        int flag = 0;
        for (int i = 0; i < G[y].size(); i++) {
            if (DP(x, G[y][i], 0) == 0) {
                flag = 1;
                break;
            }
        }
        dp[x][y][who] = flag;
    }

    visited[x][y][who] = false;
    return dp[x][y][who];
}

void solve() {
    if (DP(x, y, 0) == 1) {
        printf("Case #%d: Yes\n", ++cCase);
    } else {
        printf("Case #%d: No\n", ++cCase);
    }
}

int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
    }
    return 0;
}