原题：The Problem to Make You Happy
原题大意
Bob和Alice在有向图内玩游戏，n个顶点，m条边。
每人一颗棋子，初始位置分别是x，y。
Bob先手，轮流操作，每次只能走一条有向边。
结束条件: 1.不能操作的人输 2.两个棋子重合Bob输 3.游戏没有尽头Alice输
问 Bob 能不能赢？
2 <= n <= 100. 1 <= m <= n <= n*(n-1) 1 <= x , y <= n, x != y.
算法分析
- 状态设计：两颗棋子的位置，下一步棋是谁走。因子我们可以用
dp[x][y] [0/1]表示两枚棋子的状态,Alice在x，Bob在y处，0是下一步Alice走，1是下一步Bob走。 - 思路：通过BFS，进行状态之间的转移。
- 初始状态：两颗棋子重叠为必败状态，先令这些状态在dp数组中的
值为0，其它的为1 - 状态转移：
a) 若是选手A打算行动，那么在他之前行动的是B，要让B能GG
必须B能到达的所有状态均为必败。
b) 若是选手B打算行动，那么在他之前行动的是A，时光倒流，
A行动时的那个状态一定可以让B输掉比赛
程序代码
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 105;
struct Pair{
int x, y, s;
//简化赋初值
Pair(int x_, int y_, int s_){
x = x_;
y = y_;
s = s_;
}
};
int T, Bob_pos, Alice_pos, m, n, kase, u, v;
vector<int> G1[maxn];//记录有向图
vector<int> G2[maxn];//逆着记录有向图，便于由必败叶子节点状态转移回来
int dp[maxn][maxn][2], vis[maxn][maxn][2], cnt[maxn][maxn][2], deg[maxn];
//vis记录Bob必败的状态是否确定，若确定记为1，否则为0
//cnt与deg组合使用，cnt记录当前状态被访问的次数，deg为出度，若两者相等则此状态为Bob必败状态
queue<Pair>q;
//初始化
void Init(){
for(int i = 1; i <= n; i++)
{
deg[i] = 0;
for(int j = 1; j <= n; j++)
{
for(int k = 0; k < 2; k++)
{
dp[i][j][k] = 1;
vis[i][j][k] = cnt[i][j][k] = 0;
}
}
G1[i].clear();
G2[i].clear();
}
while(!q.empty()) q.pop();
}
int main(){
scanf("%d", &T);
kase = 0;
while(T--){
scanf("%d %d", &n, &m);
Init();
for(int i = 0; i < m; i++){
scanf("%d %d", &u, &v);
G1[u].push_back(v);
G2[v].push_back(u);
deg[u]++;
}
scanf("%d %d", &Bob_pos, &Alice_pos);
for(int i = 1;i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 0; k < 2; k++){
if(i == j || (k == 1 && G1[j].size() == 0))
{
dp[i][j][k] = 0;
Pair t(i, j, k);
q.push(t);
vis[i][j][k] = 1;
}
}
while(!q.empty()){
Pair now = q.front(); q.pop();
int cx = now.x, cy = now.y, cs = now.s;
if(cs == 0)
{
for(int i = 0; i < G2[cy].size(); i++)
{
int pre = G2[cy][i];
if(vis[cx][pre][1] == 1) continue;
cnt[cx][pre][1]++;
if(cnt[cx][pre][1] == deg[pre])
{
dp[cx][pre][1] = 0;
vis[cx][pre][1] = 1;
Pair t(cx, pre, 1);
q.push(t);
}
}
}
else if(cs == 1)
{
for(int i = 0; i < G2[cx].size(); i++)
{
int pre = G2[cx][i];
if(vis[pre][cy][0] == 1) continue;
dp[pre][cy][0] = 0;
vis[pre][cy][0] = 1;
Pair t(pre, cy, 0);
q.push(t);
}
}
}
if(dp[Alice_pos][Bob_pos][1] == 1)
printf("Case #%d: Yes\n", ++kase);
else
printf("Case #%d: No\n", ++kase);
}
return 0;
}