作业问题（Assignment Problem）

问题描述

给定一个 $N \times N$ 的矩阵 $a_{ij}$，求一个排列 $p$（即 $p_0, p_1, \dots, p_{N-1}$ 是 $0$ 到 $N-1$ 的一个排列），使得

最小。

若存在多个最优解，输出任意一个。

约束条件

• $1 \leq N \leq 500$
• $|a_{ij}| \leq 10^9$

输入

$N$
$a_{00}\ a_{01}\ \cdots\ a_{0,N-1}$
$a_{10}\ a_{11}\ \cdots\ a_{1,N-1}$
:
$a_{N-1,0}\ a_{N-1,1}\ \cdots\ a_{N-1,N-1}$

输出

$X$
$p_0\ p_1\ \cdots\ p_{N-1}$

$X = \sum_{i=0}^{N-1} a_{i, p_i}$ 是最小总代价。

3
4 3 5
3 5 9
4 1 4

9
2 0 1