#CS2129. 任务分配

任务分配

题目背景

翻译自 CSES-2129 题。

题目描述

一家公司有n个员工，且有n个任务需要完成。我们知道每个员工执行每个任务的费用。每个员工必须被分配一个任务。请问，如何最优分配任务，使得总费用最小，并给出任务的具体分配方案。

输入格式

第一行包含一个整数n：表示员工的数量，同时也表示任务的数量。

接下来的n行中，每行包含n个整数，表示每个员工执行每个任务的费用。第i行中的第j个整数cijc_{ij}cij​表示第i个员工执行第j个任务的费用。

输出格式

首先输出最小的总费用。

然后输出n行，每行包含两个整数a和b，表示第a个员工被分配了第b个任务。

如果有多个最优解，可以输出任意一个。

样例

4
17 8 16 9
7 15 12 19
6 9 10 11
14 7 13 10

33
1 4
2 1
3 3
4 2

样例1解释 最小的总费用是3。我们可以通过以下分配方案达到最优：

• 第1个员工执行第4个任务，费用为9；

• 第2个员工执行第1个任务，费用为7；

• 第3个员工执行第3个任务，费用为101010；

• 第4个员工执行第2个任务，费用为7。

总费用为9+7+10+7=339 + 7 + 10 + 7 = 339+7+10+7=33。

说明/提示

$1 \leq n \leq 200$

1≤cij≤101 \leq c_{ij} \leq 101≤cij​≤10。