Responsive image

问题 E: 军阵演习

问题 E: 军阵演习

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

军阵演习是小说与电视中经常出现的桥段，主角总能在其中大发光彩夺得头筹。但事实并非如此简单，就好比人员的调度就十分讲究。现在考考聪明的你：假如你有n个营地，每个营地初始有ai个人，经过一番调配后每个营地至少要有bi个人。现在拥有地图的你怎么才能花费最少的情况完成调度？

输入描述

第一行：   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 ≤ 106)

输出描述

输出调度后的最小费用。

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

样例输入

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

样例输出

9
[提交][状态]
ACM算法攻关部