获得最大分数

Question

给出了一个n*n矩阵。

行表示学生，相应的列表示在该特定论文中获得的标记。

例如->

n=3

1 2 3 

4 5 6

7 8 9

然后，第一名学生在第一篇论文中得了1分，在第二篇论文中获得2分，等等。

第二名学生在第一篇论文中得了4分，在第二篇论文中得了5分等等。

给出->每个学生只会得到一张试卷来解决

按照上述条件，我们需要使n名学生获得的总分最大化。

对于上述输入，输出->>(8+6+1)=15。

约束->

1<=n<=100

My approach->

I thought to solve it using dp+bitmask but n can be as large as 100 so had to drop this idea.

Answer 1

这是一个典型的加权二部图问题，可以用KM算法(匈牙利算法)来解决。

为了构造二分，我们把所有的学生放在一套，所有的试卷在另一组。我们将学生连接到具有价值X边缘的试卷，其中X是学生在该考试中可以获得的分数。在构造了图之后，只需运行KM算法，您就会得到答案。

这里有一个顶级编码器教程，它很好地解释了这类问题，并给出了一个代码模板。你可以从这里开始:)