3676 . [模板題] Assignment Problem
TopCoder
Tags
Description
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.
Input Format
$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 Format
$X$
$p_ 0$ $p_ 1$ ... $p_ {N-1}$
$X = \sum_ {i = 0}^ {N - 1} a_ {ip_ i}$
Sample Input 1
3 4 3 5 3 5 9 4 1 4
Sample Output 1
9 2 0 1
Hints
- $1 \leq N \leq 500$
- $|a_ {ij}| \leq 10^ {9}$
Note that timelimit is different from https://judge.yosupo.jp/problem/assignment
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|