Assignment Problem

AC一覧

Problem Statement
問題文

Given $N \times N$ matrix $a_{ij}$. Calculate a permutation $p_i$ that minimize $\sum_{i = 0}^{N - 1} a_{ip_i}$.

If there is multiple solutions, print any of them.

$N \times N$ の行列 $a_{ij}$ が与えられる。 $\sum_{i = 0}^{N - 1} a_{ip_i}$ を最小化する順列 $p_i$ を構成してください。

解が複数あるときはどれを出力してもいいです。

Constraints
制約

Input
入力

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

Output
出力

$X$
$p_0$ $p_1$ ... $p_{N-1}$

$X = \sum_{i = 0}^{N - 1} a_{ip_i}$

Sample
サンプル

# 1

3
4 3 5
3 5 9
4 1 4
9
2 0 1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions