algorithm - 最大化获得的分数

Question

给定一个n*n矩阵。

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

例如->

n=3

1 2 3 

4 5 6

7 8 9

然后第一个学生在第 1 篇论文中得 1 分，在第 2 篇论文中得 2 分，依此类推。

第 2 名学生在第 1 篇论文中获得 4 分，在第 2 篇论文中获得 5 分，依此类推。

given->每个学生只会得到一份试卷来解决

根据上述条件，我们需要最大化 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

这是一个典型的 weighted bipartite graph问题，可以使用 KM algorithm (Hungarian algorithm) 解决.

为了构建二分法，我们将所有学生放在一组中，将所有试卷放在另一组中。我们将学生连接到具有边值 X 的试卷，其中 X 是学生在该考试中可以获得的分数。图构建完成后，运行KM算法即可得到答案。

这是一个tutorial from top coder很好的解释了这类问题，还给出了代码模板。你可以从这里开始:)