P4015 运输问题

    • 383通过
    • 590提交
  • 题目提供者 zzlzk
  • 评测方式 云端评测
  • 标签 SPFA 图的建立,建图 最大流 网络流24题 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

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

    推荐的相关题目 显示

    题目描述

    $W$ 公司有 $m$ 个仓库和 $n$ 个零售商店。第 $i$ 个仓库有 $a_i$ 个单位的货物;第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

    货物供需平衡,即$\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$。

    从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{ij}$​​ 。

    试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

    输入输出格式

    输入格式:

    第 $1$ 行有 $2$ 个正整数 $m$ 和 $n$,分别表示仓库数和零售商店数。

    接下来的一行中有 $m$ 个正整数 $a_i$,表示第 $i$ 个仓库有 $a_i$个单位的货物。

    再接下来的一行中有 $n$ 个正整数 $b_j$,表示第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

    接下来的 $m$ 行,每行有 $n$ 个整数,表示从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用 $c_{ij}$。

    输出格式:

    两行分别输出最小运输费用和最大运输费用。

    输入输出样例

    输入样例#1: 复制
    2 3
    220 280
    170 120 210
    77 39 105
    150 186 122
    输出样例#1: 复制
    48500
    69140

    说明

    $1 \leq n, m \leq 100$

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