题目描述
给定一个 n 个点 m 条边的有向弱连通图, 每个点均有点权 di 和修改耗时 wi, 每次修改可以花费 wi 的时间把 di 加 1 或者减 1,求最少消耗多少时间,使得 ∀(u,v)∈E,du≤dv。
输入格式
输入共包括 m+3 行
第一行包含两个整数 n,m,表示点数和边数。
第二行包含 n 个整数,第 i 个整数表示第 i 个点的点权 di。
第三行包含 n 个整数,第 i 个整数表示第 i 个点的修改耗时 wi。
第 4 m+3 行,每行包含两个整数 ui,vi,表示有向图种的一条由 ui 到 vi 的有向边。
输出格式
输出包含一个整数,表示最小总耗时。
样例 1
3 3
5 9 8
1 2 3
1 2
2 3
3 1
5
限制为 d1≤d2,d2≤d3,d3≤d1,即要求 d1=d2=d3,故将 d1 加 3 至 8,d2 减 1 至 8 最优,最小耗时为 1×∣5−8∣+2×∣9−8∣+3×∣8−8∣=5。
3 2
5 9 8
1 2 3
1 2
2 3
2
数据范围与提示
子任务 |
分值 |
n≤ |
m= |
特殊限制 |
1 |
10 |
5000 |
n−1 |
无 |
2 |
20 |
100000 |
将所有有向边看成无向边时,整张图构成一条链 |
3 |
20 |
无 |
4 |
15 |
300000 |
5 |
10 |
n |
存在数列fi,满足有且仅有i向fi的有向边,wi=1 |
6 |
10 |
将所有有向边看成无向边时,整张图构成一个环 |
7 |
15 |
n−1,n |
无 |