跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0250. #6011. 「网络流 24 题」运输问题

  • ID: 256
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 网络流
  • 图论
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#6011. 「网络流 24 题」运输问题

题目描述

W 公司有 个仓库和 个零售商店。第 个仓库有 个单位的货物;第 个零售商店需要 个单位的货物。货物供需平衡,即 。从第 个仓库运送每单位货物到第 个零售商店的费用为 。试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

输入格式

第 行有 个正整数 和 ,分别表示仓库数和零售商店数。接下来的一行中有 个正整数 ,表示第 个仓库有 个单位的货物。再接下来的一行中有 个正整数 ,表示第 个零售商店需要 个单位的货物。接下来的 行,每行有 个整数,表示从第 个仓库运送每单位货物到第 个零售商店的费用 。

输出格式

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

样例

样例输入

2 3
220 280
170 120 210
77 39 105
150 186 122

样例输出

48500
69140

数据范围与提示


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 142 题。保留原作者与原赛事署名。