P4014 Assignment Problem

There are $n$ jobs to be assigned to $n$ people. When person $i$ does job $j$, the benefit is $c_{ij}$. Design an assignment that assigns $n$ jobs to $n$ people so that the total benefit is minimized or maximized.

The first line contains one positive integer $n$, indicating there are $n$ jobs to be assigned to $n$ people. In the next $n$ lines, each line contains $n$ integers $c_{i,j}$, where $c_{i,j}$ is the benefit when person $i$ does job $j$.

Output two lines: the minimum total benefit and the maximum total benefit, respectively.

$1 \leq n \leq 50, 0 \le c _ {i, j} \le 100$. Each person can do only one job. Translated by ChatGPT 5