怎么做企业的网站,建筑工程承包网app,昆明官渡区网站建设,网站建设 大公司好P4055 [JSOI2009]游戏
对于一个网格#xff0c;上面有一些障碍物不能走#xff0c;A选择起点#xff0c;然后B走到相邻的四个格子之一#xff0c;然后轮流移动不能移动的一方失败。求解所有可以赢的初始位置。
首先对于这个问题要想到网格图上博弈#xff0c;两个人走的…P4055 [JSOI2009]游戏
对于一个网格上面有一些障碍物不能走A选择起点然后B走到相邻的四个格子之一然后轮流移动不能移动的一方失败。求解所有可以赢的初始位置。
首先对于这个问题要想到网格图上博弈两个人走的格子奇偶性不同所以可以建立二分图然后轮流移动现在要求解一个位置满足后手必胜。
那么我们发现这个位置一定不能够在最大匹配上然后我们只需要求出所有不在最大匹配上的点但是最大匹配可能有很多方案我们需要求出所有方案下都不在最大匹配上的点。
具体方法就是先求解最大匹配然后对于不在上面的点进行dfs然后如果能够回到同一边那么将这条路径取反就得到了一条不同的最大匹配那么这个点就是不合法的。这样就可以得到一定不在最大匹配上的点。
求解一定不在最大匹配上的点求出一个最大匹配dfs检验
