Problem
あなたはn個の異なる仕事をする必要があります。この場合、n 人の便利屋のリストと、どの労働者がどの作業を何ドルで行うかのリストがあります。
ワーカーを分散して、合計でより少ない費用を費やすようにします。同時に、すべてを 1 日で実行したいので、ワーカーは並行して作業します。したがって、各ワーカーは正確に 1 つのタスクを実行します。
入力:
最初の行では、正の数 n (1 <= n <= 8) - ジョブとワーカーの数が与えられます。
次の n 行には、スペースで区切られた n 個の正の整数が含まれています - 行列 A、ここで A
i,j は、番号 i のワーカーが番号 j の作業を行う金額を示します。すべての A
i,j に対して 1 <= A
i,j <= 10
5.
出力:
単一の数字を出力してください - すべての利用可能な仕事のためにこれらの労働者を雇うことができる最低コスト.
例:
<本体>
| 入力 |
出力 |
3
3 1 2
5 6 4
7 8 9
| 12 |
説明:
最初のワーカーが 2 番目のジョブを実行し、2 番目のワーカーが 3 番目のジョブを実行し、3 番目のワーカーが最初のジョブを実行します。合計コストは 1 + 4 + 7 = 12 です。