nyoj 1367 ZZNUOJ 2109 物流配送

  • 2018-10-05
  • 11
  • 0

Description:

物流配送是物流活动中一种非单一的业务形式,它与物品流动、资金流动紧密结合。备货是配送的准备工作或基础工作,备货工作包括筹集货源、订货或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一,就是可以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作,如果备货成本太高,会大大降低配送的效益。配送中的储存有储备及暂存两种形态。配送储备是按一定时期的配送经营要求,形成的对配送的资源保证。这种类型的储备数量较大,储备结构也较完善,视货源及到货情况,可以有计划地确定周转储备及保险储备结构及数量。

Dr. Kong 所在的研究团队准备为Hai-E集团开发一个物流配送管理系统。已知Hai-E集团已经在全国各地建立了n个货物仓库基地,任意两个基地的货物可以相互调配。现在需要根据用户订货要求,来重新调配每个基地的货物数量。为了节流开源,希望对整个物流配送体系实行统一的货物管理和调度,能够提供一个全面完善的物流仓储配送解决方案,以减少物流配送过程中成本、人力、时间。

Input:

第一行: n (1 ≤ n ≤ 1000)

第2行: a1 a2 …… an 表示n个基地当前的物品数量 (0≤ ai ≤ 106 )

第3行: b1 b2 …… bn 表示调配后,每个基地i应不少于bi个物品 (0≤ bi ≤ 106)

接下来n-1行,每行三个整数: i j k 表示从第i基地调配一个物品到第j基地需要花费为k,或 从第j基地调配一个物品到第i基地需要花费为k。(0≤ k ≤ 10^6)

Output:

输出配送后的最小费用。

已知: a1+a2+…+an >=b1+b2+…+bn

Sample Input:

6
0 1 2 2 0 0
0 0 1 1 1 1
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1

Sample Output:

9

题目链接

题目很明显的最小费用最大流裸题,要求出最后重新调配每个基地货物数量之后的最小花费,建图时源点连接每个货物仓库基地,容量为a[i]花费为0(初始时每个货物仓库基地有a[i]个货物),每个货物仓库基地链接汇点,容量为b[i]花费为0(因为要求最小化费,显然最大流为\sum_{i=1}^{n}b_{i}),最后在可调配路线上建边跑最小费用最大流即可,此题数据会爆int。

AC代码:

评论

还没有任何评论,你来说两句吧