#1760. 有向图
有向图
有向图
题目描述
标题: 有向图 - Problem - QOJ.ac
#4785. 有向图
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 无
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 3
5 9 8
1 2 3
1 2
2 3
3 1
5
样例 2
3 2
5 9 8
1 2 3
1 2
2 3
2