本文共 584 字，大约阅读时间需要 1 分钟。

如何让n个管理员选择n个工作人员，使得每个人的平均评价值最小？

首先，我们需要理解题目中的评价值系统。每个管理员对每个工作人员的评价值从0到n-1，其中0代表最高评价，n-1代表最低评价。同样，每个工作人员对每个管理员的评价也是从0到n-1，0代表最高，n-1代表最低。评价值是双向的，管理员对工作人员的评价值和工作人员对管理员的评价值相加即为总的评价值。

这个问题可以转化为一个最小权匹配问题。在一个完全图中，节点代表管理员和工作人员，边的权重为管理员对工作人员的评价值加上工作人员对管理员的评价值。我们需要找到一个完美匹配，使得所有边的权重之和最小。

使用Kuhn-Munkres（KM）算法来求解这个最小权匹配问题，可以找到最优的配对方式。KM算法通过多次DFS搜索，逐步松弛边的权重，直到找到最优匹配。

在KM算法之后，除了找到最小权匹配，还需要对所有可能的匹配进行DFS搜索，以找到所有满足条件的匹配，并按照字典序排列。

总结来说，解决这个问题的步骤如下：

通过上述步骤，我们可以找到使得每个人的平均评价值最小的管理员和工作人员配对方式。

转载地址：http://oetfk.baihongyu.com/