工作分配问题

题目描述

有 $n$ 个人从事 $n$ 项工作，每个人对于不同工作的收益有所不同，但每个人只能从事一项工作，且每个工作只能由一个人做，他们想知道他们能获得的总体最大效益是多少？

输入格式

第一行输入一个 $n$，表示 $n$ 个人从事 $n$ 项工作，其中 $1 \le n \le 20$。

接下来有 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数表示第 $i$ 个人从事第 $j$ 个工作所能获得的收益，每个整数在 $1 \sim 100$ 之间。

输出格式

一个整数，输出他们能够得到的最大总收益。

样例输入 #1

5
13 11 10 4 7
13 10 10 8 5
5 9 7 7 4
15 12 10 11 5
10 11 8 8 4

样例输出 #1

50

数据范围

$1 \le n \le 20$，收益值在 $1 \sim 100$ 之间。

知识点与难度

本题涉及搜索与状态压缩动态规划，从属于 GESP六级，难度等级：⭐⭐⭐。

测试点分布