Minimum Cost
Time Limit: 4000MS |
|
Memory Limit: 65536K |
Total Submissions: 8593 |
|
Accepted: 2825 |
Description
Dearboy, a goods victualer, now comes to a big
problem, and he needs your help. In his sale area there are N shopkeepers
(marked from 1 to N) which stocks goods from him.Dearboy has M supply places
(marked from 1 to M), each provides K different kinds of goods (marked from 1 to
K). Once shopkeepers order goods, Dearboy should arrange which supply place
provide how much amount of goods to shopkeepers to cut down the total cost of
transport.
It's known that the cost to transport one unit goods for
different kinds from different supply places to different shopkeepers may be
different. Given each supply places' storage of K kinds of goods, N shopkeepers'
order of K kinds of goods and the cost to transport goods for different kinds
from different supply places to different shopkeepers, you should tell how to
arrange the goods supply to minimize the total cost of transport.
Input
The input consists of multiple test cases. The first
line of each test case contains three integers N, M, K (0 < N, M, K < 50),
which are described above. The next N lines give the shopkeepers' orders, with
each line containing K integers (there integers are belong to [0, 3]), which
represents the amount of goods each shopkeeper needs. The next M lines give the
supply places' storage, with each line containing K integers (there integers are
also belong to [0, 3]), which represents the amount of goods stored in that
supply place.
Then come K integer matrices (each with the size N * M),
the integer (this integer is belong to (0, 100)) at the i-th row, j-th column in
the k-th matrix represents the cost to transport one unit of k-th goods from the
j-th supply place to the i-th shopkeeper.
The input is terminated with
three "0"s. This test case should not be processed.
Output
For each test case, if Dearboy can satisfy all the
needs of all the shopkeepers, print in one line an integer, which is the minimum
cost; otherwise just output "-1".
Sample Input
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
Sample Output
4
-1
Source
分享到:
相关推荐
pku部分题代码,不多,试一下怎么上传文件!
pku1000 pku1000程序 解题报告
pku经典题目解题报告 pku经典题目解题报告
pku1664源代码
PKU JudgeOnline FAQ 中文版 常见问题解答
8数码代码pku1077,300ms(哈希+广度搜索)
ppt word PKU 课件 五星级灰常强大
ACM代码 北大pku。 搞ACM的可以参考一下。代码还是挺规范的。有接近150道题目的代码。
benchmark (PKU-MMD) for continuous multi-modality 3D human action understanding and cover a wide range of complex human activities with well annotated information. PKU-MMD contains 1076 long video ...
PKU 2339 Rock, Scissors, Paper 源代码
有一些代码是pku上的,希望大家看后给我留言,看看我的代码那里有问题??
pku acm 1469 COURSES 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
这是关于PKU上的题目分类 很详细 适合不同水平的童鞋们参考
北京大学pku2317 Questions and answers c++标程 文件名为2371.cpp
我写的解题报告,关于度限制生成树的 网址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1639<br>题目:Picnic Planning 来源:East Central North America 2000
PKU的oj分类 可以通过分类进行练习~~~
分词训练用的pku训练集,主要是说明相似度计算的样例数据。
pku acm 1042 贪心法
pku2482--Stars in Your Window的源程序