Responsive image

问题 1488 --能 源 公 司

1488: 能 源 公 司

时间限制: 1 Sec  内存限制: 65535 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

ZDM能源公司现有一个火力发电厂和M座煤矿。火力发电厂每年需要用煤T吨。该火力发电厂每年正常运作的固定费用为R元（包括人员工资，折旧费，不包括煤的运费）。第I号煤矿每年产量为ai吨，每吨原煤从第I号煤矿运到该火力发电厂的运费为Ci0。

ZDM能源公司现在准备再建立一个火力发电厂，M座煤矿每年开采的原煤将全部供给这两座发电厂。现有N个备选的地址建厂。若在第J号备选地址建厂，新建发电厂每年正常运作的固定费用每年运行的固定费用为hj元。每吨原煤从第I号矿运到J号备选厂址的运费为Cij。

现在的问题是，把新厂地址选取什么位置，M座煤矿开采的原煤应如何分配给两个发电厂，才能使ZDM能源公司每年的总费用（发电厂运行费用与原煤运费之和）达到最小。

输入描述

第1行： M T R N
第2行： a1 a2 … am
第3行： h1 h2 … hn
第4行： C10 C20 … Cm0
第5行： C11 C21 … Cm1
… …
第n+4行： C1n C2n … Cmn


【约束条件】
1≤M≤100000 1≤T≤10000 1≤R≤50 1≤N≤50
0≤ai≤500, a1+a2+...+am>=T 0≤ hj ≤100 0≤Ci0，Cij ≤50
所有数据都是整数。 数据之间有一个空格。 i=1,2,…., m j=1,2,…, n

输出描述

第1行：新厂址编号，如果有多个编号满足要求，输出最小的。
第2行：总费用

样例输入

4 2 7 9 
3 1 10 3 
6 3 7 1 10 2 7 4 9 
1 2 4 3 
6 6 8 2 
4 10 8 4 
10 2 9 2 
7 6 6 2 
9 3 7 1 
2 1 6 9 
3 1 10 9 
4 2 1 8 
2 1 3 4

样例输出

8
49

提示

  河南省第六届ACM程序设计大赛

来源

第六届省赛 

[提交][状态]
ACM算法攻关部