1709: 删边问题（洛谷：P9424 [蓝桥杯 2023 国 B]）

给定一个包含 $N$ 个结点 $M$ 条边的无向图 G，结点编号 $1\cdots N$。其中每个结点都有一个点权 Wi。

你可以从 $M$ 条边中任选恰好一条边删除，如果剩下的图恰好包含 $2$ 个连通分量，就称这是一种合法的删除方案。

对于一种合法的删除方案，我们假设 $2$ 个连通分量包含的点的权值之和分别为 $X$ 和 $Y$，请你找出一种使得 $X$ 与 $Y$ 的差值最小的方案。输出 $X$ 与 $Y$ 的差值。

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，W1,W2,⋯,WN。

以下 $M$ 行每行包含 $2$ 个整数 $U$ 和 $V$，代表结点 $U$ 和 $V$ 之间有一条边。

4 4
10 20 30 40
1 2
2 1
2 3
4 3

20

由于 $1$ 和 $2$ 之间实际有 $2$ 条边，所以合法的删除方案有 $2$ 种，分别是删除 $(2,3)$ 之间的边和删除 $(3,4)$ 之间的边。

删除 $(2,3)$ 之间的边，剩下的图包含 $2$ 个连通分量：$\{1,2\}$ 和 $\{3,4\}$，点权和分别是 $30$、$70$，差为 $40$。

删除 $(3,4)$ 之间的边，剩下的图包含 $2$ 个连通分量：$\{1,2,3\}$ 和 $\{4\}$，点权和分别是 $60$、$40$，差为 $20$。

评测用例规模与约定

• 对于 $20\%$ 的数据，$1\le N,M\le 10000$。
• 对于另外 $20\%$ 的数据，每个结点的度数不超过 $2$。
• 对于 $100\%$ 的数据，$1\le N,M\le 200000$，0≤Wi≤109，$1\le U,V\le N$。

算法标签：强连通分量