#PQJ126x4785. QOJ 126_4785

    ID: 2583 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:集训队互测 2018图论

QOJ 126_4785

标题: 有向图 - Problem - QOJ.ac

#4785. 有向图

Statistics

The problem was used in the following contests:

给定一个 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

样例 1 输出

5

样例 1 解释

限制为 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。

样例 2 输入

3 2
5 9 8
1 2 3
1 2
2 3

样例 2 输出

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 无