军阵演习是小说与电视中经常出现的桥段，主角总能在其中大发光彩夺得头筹。但事实并非如此简单，就好比人员的调度就十分讲究。现在考考聪明的你：假如你有n个营地，每个营地初始有ai个人，经过一番调配后每个营地至少要有bi个人。现在拥有地图的你怎么才能花费最少的情况完成调度？
问题 E: 军阵演习
时间限制: 1 Sec 内存限制: 128 MB提交: 4 解决: 3
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行： 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)
第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-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版