TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2656
  • 题目
  • P2656【HAOI2010 Day1】工厂选址
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    某地区有m左煤矿,其中第i号矿每年产量为ai吨,现有火力发电站一个,每年需用煤b吨,每年运行的固定费用(包括折旧费,不包括煤的运费)为h元,每吨原煤从第i号矿运到原有发电厂的运费为Ci0(i=1,2,…,m;j=1,2,…,n)。
    现规划新建一个发电厂,m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂,每年运行的固定费用为hi元。每吨原煤从第i号矿运到j号备选厂址的运费为Cij(i=1,2,…,m;j=1,2,…,n)。
    试问:应把新厂厂址选取在何处?m座煤矿开采的原煤应如何分配给两个发电厂,才能使每年的总费用(发电厂运行费用与原煤费用之和)为最小。

    输入格式

    第1行: m b h n
    第2行: a1 a2 … am (0<=ai<=500,a1+a2+…+an>=b)
    第3行: h1 h2 … hn (0<=hi<=100)
    第4行: C10 C20 … Cm0 (0<=Cij<=50)
    第5行: C11 C21 … Cm1
    … …
    第n+4行:C1n C2n … Cmn

    输出格式

    第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

    提示

    对于30%的数据,n<=50,m<=100,b<=100
    对于60%的数据,n<=50,m<=100,b<=10000
    对于所有数据,n<=50,m<=50000,b<=10000
    大规模输入数据,对于C++,谨慎使用cin/cout.推荐采用scanf和printf.


    来源  HeNanOI 2010