7151. 任务分配 (Task Assignment)
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 某公司有 $n$ 名员工以及 $n$ 项需要完成的任务。我们已知每名员工完成每项任务所需的成本。 每名员工必须被精确分配给一项任务，且每项任务也只能分配给一名员工。如果采取最优的任务分配策略，最小的总成本是多少，该如何具体分配？ ## 输入格式 第一行包含一个整数 $n$，表示员工数量和任务数量。 接下来 $n$ 行，每行包含 $n$ 个整数。其中第 $i$ 行包含整数 $c\_{i1}, c\_{i2}, \dots, c\_{in}$，分别表示将各项任务分配给第 $i$ 名员工时的成本。 ## 输出格式 第一行输出一个整数，表示最小的总成本。 随后输出 $n$ 行，每行包含两个整数 $a$ 和 $b$，代表将第 $b$ 个任务分配给第 $a$ 名员工。如果存在多种最优方案，输出其中任意一种即可。 ## 输入输出样例 ### 输入 #1 ``` 4 17 8 16 9 7 15 12 19 6 9 10 11 14 7 13 10 ``` ### 输出 #1 ``` 33 1 4 2 1 3 3 4 2 ``` ### 样例解释 最小的总成本是 $33$。可以通过以下分配获得：员工 1 分配任务 4，员工 2 分配任务 1，员工 3 分配任务 3，员工 4 分配任务 2。 总成本为：$9 + 7 + 10 + 7 = 33$。 ## 说明/提示 ### 数据规模与约定 * $1 \le n \le 200$ * $1 \le c\_{ij} \le 1000$