#P2516. Minimum Cost

Minimum Cost

题目描述:

Dearboy 是一名商品供应商,现在遇到了一个大问题,需要你的帮助。在他的销售区域中有 NN 个店主(编号从 11NN),他们从 Dearboy 那里进货。Dearboy 有 MM 个供应点(编号从 11MM),每个供应点提供 KK 种不同的商品(编号从 11KK)。每当店主们下单时,Dearboy 需要安排从各个供应点向各个店主运送多少数量的商品,以最小化运输的总成本。

已知不同种类的商品从不同供应点运送到不同店主的单位运输成本可能不同。给定每个供应点存储的 KK 种商品的数量、每个店主订购的 KK 种商品的数量,以及不同种类商品从不同供应点到不同店主的运输成本,你需要计算出如何安排商品供应才能使运输总成本最小。

输入格式:

输入包含多个测试用例。每个测试用例的第一行包含三个整数 NNMMKK0<N,M,K<500 < N, M, K < 50),含义如上所述。接下来的 NN 行给出店主的订单,每行包含 KK 个整数(这些整数属于 [0,3][0, 3]),表示每个店主对每种商品的需求量。接下来的 MM 行给出供应点的库存,每行包含 KK 个整数(这些整数也属于 [0,3][0, 3]),表示该供应点存储的每种商品的数量。

然后是 KK 个整数矩阵(每个矩阵的大小为 N×MN \times M),第 kk 个矩阵中第 ii 行第 jj 列的整数(该整数属于 (0,100)(0, 100))表示将第 kk 种商品的单位从第 jj 个供应点运输到第 ii 个店主的成本。

输入以三个 00 结束,该测试用例无需处理。

输出格式:

对于每个测试用例,如果 Dearboy 能够满足所有店主的所有需求,则在一行中输出一个整数,表示最小成本;否则输出 1-1

输入数据 1:

1 3 3  
1 1 1
0 1 1
1 2 2
1 0 1
1 2 3
1 1 1
2 1 1

1 1 1
3
2
20

0 0 0

输出数据 1:

4
-1