LibreOJ

2470 「2018 集训队互测 Day 2」有向图

内存限制：512 MB 时间限制：3000 ms

题目描述

给定一个 $n$ 个点 $m$ 条边的有向弱连通图， 每个点均有点权 $d_i$ 和修改耗时 $w_i$， 每次修改可以花费 $w_i$ 的时间把 $d_i$ 加 $1$ 或者减 $1$，求最少消耗多少时间，使得 $\forall (u,v)\in E, d_u\le d_v$。

输入格式

输入共包括 $m+3$ 行
第一行包含两个整数 $n,m$，表示点数和边数。
第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的点权 $d_i$。
第三行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的修改耗时 $w_i$。
第 $4 ~ m+3$ 行，每行包含两个整数 $u_i,v_i$，表示有向图种的一条由 $u_i$ 到 $v_i$ 的有向边。

输出格式

输出包含一个整数，表示最小总耗时。

样例 1

限制为 $d_1\le d_2,d_2\le d_3,d_3\le d_1$，即要求 $d_1 = d_2 = d_3$，故将 $d_1$ 加 $3$ 至 $8$，$d_2$ 减 $1$ 至 $8$ 最优，最小耗时为 $1 \times |5-8| + 2\times |9-8| + 3 \times |8-8| = 5$。

样例 2

数据范围与提示

| 子任务 | 分值 | $n \leq $ | $m=$ | 特殊限制 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10$ | $5000$ | $n-1$ | 无 | | $2$ | $20$ | $100000$ | $n-1$ | 将所有有向边看成无向边时，整张图构成一条链 | | $3$ | $20 $ | $100000$ | $n-1$ | 无 | | $4$ | $15$ | $300000$ | $n-1$ | 无 | | $5$ | $10$ | $300000$ | $n$ | 存在数列$f_i$,满足有且仅有$i$向$f_i$的有向边，$w_i=1$ | | $6$ | $10 $ | $300000$ | $n$ | 将所有有向边看成无向边时，整张图构成一个环 | | $7$ | $15$ | $300000$ | $n-1,n$ | 无 |

样例

样例输入 1

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

样例输出 1

5

样例输入 2

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

样例输出 2

2