Task Assignment

题目描述

一家公司有 n 名员工，需要完成 n 项任务。我们知道每位员工完成每项任务的费用。每位员工应被分配到恰好一项任务。如果我们对任务进行最优分配，最小的总费用是多少，以及应如何分配？

输入格式

第一行输入包含一个整数 n：员工人数以及需要完成的任务数。 随后有 n 行，每行包含 n 个整数。第 i 行包含整数 c_{i1},c_{i2},$\ldots$,c_{in}：当第 i 位员工被分配到各任务时的费用。

输出格式

首先输出最小的总费用。 然后输出 n 行，每行包含两个整数 a 和 b：表示将第 b 项任务分配给第 a 位员工。 如果存在多种解法，你可以输出任意一种。

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 \le n \le 200$ $1 \le c_{ij} \le 1000$ 样例解释：最小总费用是 33。我们可以通过将员工 1 分配任务 4，员工 2 分配任务 1，员工 3 分配任务 3，员工 4 分配任务 2 来达到这个值。费用为 9 + 7 + 10 + 7 = 33。

标签: CSES2129|先进技术

来源

CSES2129|先进技术