P4015 Transportation Problem

Company $W$ has $m$ warehouses and $n$ retail stores. The $i$-th warehouse has $a_i$ units of goods; the $j$-th retail store needs $b_j$ units of goods. The supply and demand are balanced, i.e., $\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$. The cost to transport each unit of goods from the $i$-th warehouse to the $j$-th retail store is $c_{i,j}$. Design a transportation plan to ship all goods from the warehouses to the retail stores so that the total transportation cost is minimized.

Line 1 contains 2 positive integers $m$ and $n$, representing the number of warehouses and retail stores, respectively. The next line contains $m$ positive integers $a_i$, where the $i$-th warehouse has $a_i$ units of goods. The following line contains $n$ positive integers $b_j$, where the $j$-th retail store requires $b_j$ units of goods. The next $m$ lines each contain $n$ integers, representing the per-unit transportation cost $c_{i,j}$ from the $i$-th warehouse to the $j$-th retail store.

Output two lines: the minimum total transportation cost and the maximum total transportation cost.

$1 \leq n, m \leq 100$. Translated by ChatGPT 5