一个分配方案 $(a_1,a_2,\ldots,a_m)$ (第 $i$ 个职位选择 $P_{i,a_i}$) 可能是最优的当且仅当不存在 $(b_1,b_2,\ldots,b_m)$ 使得 $b_i\le a_i$ 且存在 $i$ 使得 $b_i < a_i$。另一个等价的条件是存在 $i$ 使得 $a_i=1$ 且删去第 $i$ 个职位和这个人之后方案是最优的。这个可以归纳证明，充分性显然。要证明必要性，首先若存在一个职位选择的人之前有人未被选择则显然不优，因此可以假设每个职位选择的人之前的所有人都被选择。假设不存在 $i$ 使得 $a_i=1$，则我们对每个 $i$ 连边 $(P_{i,a_i},P_{i,1 })$，得到的是基环树森林，任意找一个环替换就是更优的。因此一定有一个 $i$ 满足 $a_i=1$。

因此我们可以枚举 $m!$ 个排列，依次为每个职位选择第一个未被选择的人，这样显然可以枚举所有最优方案 (当然可能重复)。

时间复杂度 $O(m!\cdot m^2)$，改用 DFS 枚举可以优化到 $O(m!\cdot m)$，但因为常数关系实践中会更慢。