AT_arc107_f.[ARC107F] Sum of Abs

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$ ，边编号为 $1$ 到 $M$ 。每个顶点 $i$ （ $1 \leq i \leq N$ ）上写有两个整数 $A_i, B_i$ 。另外，第 $i$ 条边（ $1 \leq i \leq M$ ）连接顶点 $U_i$ 和 $V_i$ 。

现在，すぬけくん可以选择删除 $0$ 个或多个顶点。删除顶点 $i$ 的代价为 $A_i$ 。与被删除顶点相连的边也会被同时删除。删除顶点后，得分的计算方式如下：

总得分等于所有连通分量得分的总和。
某个连通分量的得分为该分量内所有顶点的 $B_i$ 之和的绝对值。

すぬけくん的收益定义为 $($ 总得分 $-$ 删除顶点的总代价 $)$ 。请你求出すぬけくん可以获得的最大收益。

输入格式

输入以如下格式从标准输入读入：

$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$

输出格式

请输出すぬけくん可以获得的最大收益。

输入输出样例

输入#1
```
4 4
4 1 2 3
0 2 -3 1
1 2
2 3
3 4
4 2
```
输出#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

输入#3
```
4 2
1 1 1 1
1 1 -1 -1
1 2
3 4
```
输出#3
```
4
```

说明/提示

限制条件

$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$
图中没有自环和重边。
所有输入均为整数。

样例解释 1

如果删除顶点 $2$ ，则需要花费 $1$ 的代价。此时，图被分成两个连通分量。由顶点 $1$ 构成的连通分量得分为 $|0|=0$ ，由顶点 $3,4$ 构成的连通分量得分为 $|-3+1|=2$ 。因此收益为 $0+2-1=1$ 。无法获得比 $1$ 更大的收益，所以答案为 $1$ 。

样例解释 3

给定的图不一定是连通的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页