P2457 [SDOI2006] The Warehouse Manager's Trouble

Warehouse manager M has been very troubled lately because his boss gave him a difficult task: come up with a reasonable plan as soon as possible to reorganize the company’s warehouses. There are $n$ warehouses and $n$ types of goods. Because the goods were not well categorized when purchased, most warehouses contain multiple types of goods, which causes a lot of trouble for the workers when moving goods. Manager M’s task is to design a reasonable plan to reorganize the goods in the warehouses so that goods of the same type are stored in the same warehouse, making future management easier. During the reorganization, some goods will definitely need to be moved from one warehouse to another. The cost of each move equals the weight of the moved goods. Programming task: Please help manager M design a moving plan so that all goods are categorized properly: each type of goods occupies exactly one warehouse, or equivalently, each warehouse holds only one type of goods. At the same time, the total cost of moving the goods should be minimized.

The first line contains $n$ ($1 \le n \le 150$), the number of warehouses. The following lines describe the goods in the warehouses. For the $i$-th warehouse, line $i+1$ contains the quantities $x$ of the $n$ types of goods ($0 \le x \le 100$).

Output the minimal total cost required to reorganize all the goods as required.

Sample explanation: The plan is as follows: type $1$ goods go to warehouse $2$; type $2$ goods go to warehouse $3$; type $3$ goods go to warehouse $4$; type $4$ goods go to warehouse $1$. Translated by ChatGPT 5