分数: 900 点
问题陈述
给定一个简单的无向图 N 顶点和 M 边缘。 它的顶点有编号 1, 2, \ldots, N 及其边已编号 1, 2, \ldots, M。 在顶点上 i (1 \leq i \leq N) 两个整数 写有 A_i 和 B_i 。 边缘 i (1 \leq i \leq M) 连接顶点 U_i 和 V_i.
Snuke 选择零个或多个顶点并将其删除。 删除顶点 i 成本 A_i。 删除顶点时,与该顶点相关的边也会被删除。 的 删除顶点后的 分数 $$$v$$$ 的 计算如下:
- 分数是所有连接组件的分数之和。
- 连接分量的分数是以下总和的绝对值 连接组件中顶点的 B_i 。
Snuke 的 利润 is (分数 $$$v$$$ 的) - (成本总和)。 找出 Snuke 可以获得的最大可能利润。
约束
- 1 \leq N \leq 300
- 1 \leq M \leq 300
- 1 \leq A_i \leq 10^6
- -10^6 \leq B_i \leq 10^6
- 1 \leq U_i,V_i \leq N
- 给定的图不包含自循环或多重边。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
打印 Snuke 可以获得的最大可能利润。
样本输入 1
4 4 4 1 2 3 0 2 -3 1 1 2 2 3 3 4 4 2
示例输出 1
1
删除顶点 2 成本 1。 之后,图被分成两个连接的组件。 由Vertex组成的组件的分数 1 is |0| = 0。由顶点组成的组件的分数 3 和 4 is |(-3) + 1| = 2。 因此,Snuke 的利润为 0 + 2 - 1 = 1。 他无法获得超过 1,所以答案是 1.
示例输入 2
10 12 733454 729489 956011 464983 822120 364691 271012 762026 751760 965431 -817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880 3 1 4 1 6 9 3 8 1 6 10 5 5 6 1 5 4 3 7 1 7 4 10 3
示例输出 2
2306209
示例输入 3
4 2 1 1 1 1 1 1 -1 -1 1 2 3 4
示例输出 3
4
给定的图不一定是连通的。