基于玩家偏好的角色分配可行性判定及多项式时间算法问询

这个场景的问题属于经典的二分图匹配问题，存在多项式时间复杂度的解法，具体说明如下：

问题建模 #

你可以直接把当前的分配需求转化为二分图结构：

• 二分图左半部分的节点对应全部n名玩家
• 二分图右半部分的节点对应全部m个角色
• 当且仅当A[i][j] = true（即第i名玩家偏好第j个角色）时，在左侧第i个节点和右侧第j个节点之间连一条边
  你要找的合法分配方案，本质就是判断这个二分图中是否存在大小为n的匹配（匹配指的是没有公共顶点的边集合，刚好满足「每个玩家只分到一个角色、每个角色最多分给一个玩家、分配的都是玩家偏好角色」三个约束）。

可选的多项式算法 #

目前已有多个成熟的多项式算法可以解决这个问题，常用的两种如下：

• 匈牙利算法：针对二分图匹配场景优化的经典算法，时间复杂度为O(VE)，对应本题场景下V是玩家数加角色数n+m，E最多是n*m，整体复杂度为O(n*m(n+m))，如果采用邻接表+DFS的简化实现，大多数实际场景下可以跑出O(n*m)的运行效率，足以处理万级别的数据规模
• Hopcroft-Karp算法：匈牙利算法的优化版本，时间复杂度更低，为O(E*sqrt(V))，更适合处理大规模的匹配需求

实现逻辑 #

你可以直接套用上述算法的标准模板，最终只要计算得到的最大匹配数等于玩家总数n，就返回true，否则返回false即可。

内容的提问来源于stack exchange，提问作者Mango