给你一个 nxn 棋盘，上面有 k 个骑士（相同颜色）。有人在 k 个方格上洒了强力胶，如果骑士在其中一个方格上完成移动，它就会永远卡住。此外（这就是为什么我们不能拥有好东西的原因）有人切掉了一些方格，所以棋盘上有洞。您将获得骑士的初始位置。骑士像在普通国际象棋中一样移动，但与普通国际象棋不同的是，每回合所有的骑士都会同时移动（当然，被卡住的骑士除外）。在每一步结束时，一个方格不能被超过 1 个骑士占据。洞格也不能被骑士占据（但它们确实算作骑士可以跳过的格子）。给出一个 0(tx poly(n))-time 算法来判断是否可以使用 <
我最初的想法是将这个问题表述为一个最大流问题，并使用 Ford-Fulkerson 算法来解决它。但我不确定我的节点和边缘应该是什么。任何想法？谢谢！
所描述的问题可以如下建模为分层网络问题。网络的节点集由一个人工起始节点s和一个人工终端节点组成t。中间节点集由棋盘的k副本组成n * n，这意味着有
2 + k * n * n
共节点。想象一下s在顶部，然后是k棋盘副本的层。终端节点t将位于底部。
连接s到第一个棋盘中的初始骑士位置，并连接t到k第 -th 棋盘中马的所有所需终端位置。
对于每一个i in {1,...,k-1}将i第 -th 棋盘中的每个方格连接到棋盘中的每个方格i+1当且仅当它可以通过合法的骑士移动到达。最后，删除所有留下强力胶合正方形的边（除非t是它的尾巴）并删除所有导致洞的边。此外，每条边都被限制为允许至少0和最多的流量1。总的来说，网络最多
2 * k + k * n * n = k * ( 2 + n * n )
边缘。进一步考虑到每个方格最多被一个骑士占据，每个中间节点的流量也必须由 约束1。这可以通过将每个中间节点扩展为两个节点并通过附加边连接它们来完成，其中流量受 约束1，这导致节点和边的集合最多增长 1 倍2。
当且仅当网络允许价值流时，k骑士才能从他们的初始位置移动到他们的终端位置，其中骑士的移动顺序和实现网络的流动是双射对应的。stk