首页 > 代码库 > UVALive7042(博弈论)

UVALive7042(博弈论)

题意:

  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.

分析:

  设计状态[x][y][0/1] 表示Alice的棋子在x,Bob的棋子在y,0表示Alice下次先手,1表示Bob下次先手

  那么f[x][y][0/1]就表示该状态对于Bob来说是必胜状态还是必败状态

  考虑到Bob赢的特殊规则:游戏没有尽头

  那么对于我们所有的状态,我们可以初始默认全部都是1

  然后挑出那些刚开始显而易见的必败态(博弈树的叶子节点),从这些必败态开始扩展,能扩展到的节点都是必败态节点,这样用队列扩展结束后,每个点的胜败就知道了

  刚开始必败态:f[x][x][0/1](棋子重合Bob输) f[i][x][1] (x没有出边,Bob无法走子,输)

  考虑f[i][j][0]的转移:

    既然通过f[i][j][0]转移,就说明该状态一定是Bob的必败态,而且这个状态是Alice先手,那么说明这个状态的父节点是Bob先手

    Bob从f[i‘][j][1]走到f[i][j][0],那么现在问题就是f[i‘][j][1]是不是必败态呢?

    通过博弈的基础知识易得,Bob先手走如果走到这个必败节点,那么就必须是Bob能走到的节点全都是必败节点!

    在这里,我们可以把状态节点f[i‘][j][1]的访问次数+1,表示f[i‘][j][1]的一条出边对应的节点是必败节点

    注意f[i‘][j][1]的出边数量是i‘点的出度!所以,如果某次扩展,f[i‘][j][1]的访问次数正好为i‘点的度数,那么说明这个状态节点的所有的子节点都是Bob必败态,所以该节点也是Bob必败态

  考虑f[i][j][1]的转移

    既然通过f[i][j][1]转移,就说明该状态一定是Bob的必败态,而且这个状态是Bob先手,那么说明这个状态的父节点是Alice先手

    既然是Alice先手,能走到一个Bob必败态,那么Alice肯定要这样选择,所以直接f[i][j‘][0]是必败态

  注意bfs过程中,对状态判重

  最后结果就是f[Alice][Bob][1]

UVALive7042(博弈论)