P2514 [HAOI2010]工厂选址

    • 36通过
    • 78提交
  • 题目提供者 罗肥鱼爱吃鱼
  • 评测方式 云端评测
  • 标签 各省省选 2010 河南 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某地区有m座煤矿,其中第i号矿每年产量为ai吨,现有火力发电厂一个,每年需用煤b吨,每年运行的固定费用(包括折旧费,不包括煤的运费)为h元,每吨原煤从第i号矿运到原有发电厂的运费为Ci0(i=1,2,…,m)。

    现规划新建一个发电厂,m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂,每年运行的固定费用为hj元。每吨原煤从第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行:总费用

    输入输出样例

    输入样例#1: 复制
    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 
    输出样例#1: 复制
    8 
    49 

    说明

    对于所有数据, n<=50, m<=50000, b<=10000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。