[蓝桥杯 2023 国 B] 删边问题

题目描述

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

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

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

输入格式

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

第二行包含 $N$ 个整数，$W_1, W_2, \cdots, W_N$。

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

输出格式

一个整数代表最小的差值。如果不存在合法的删除方案，输出 $-1$。

输入输出样例

输入样例 #1

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

输出样例 #1

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 \le W_i \le 10^9$，$1 \le U, V \le N$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 F 题