{"problem":{"name":"[蓝桥杯 2023 国 B] 删边问题","description":{"content":"给定一个包含 $N$ 个结点 $M$ 条边的无向图 G，结点编号 $1 \\cdots N$。其中每个结点都有一个点权 $W_i$。 你可以从 $M$ 条边中任选恰好一条边删除，如果剩下的图恰好包含 $2$ 个连通分量，就称这是一种合法的删除方案。 对于一种合法的删除方案，我们假设 $2$ 个连通分量包含的点的权值之和分别为 $X$ 和 $Y$，请你找出一种使得 $X$ 与 $Y$ 的差值最小的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9424"},"statements":[{"statement_type":"Markdown","content":"给定一个包含 $N$ 个结点 $M$ 条边的无向图 G，结点编号 $1 \\cdots N$。其中每个结点都有一个点权 $W_i$。\n\n你可以从 $M$ 条边中任选恰好一条边删除，如果剩下的图恰好包含 $2$ 个连通分量，就称这是一种合法的删除方案。\n\n对于一种合法的删除方案，我们假设 $2$ 个连通分量包含的点的权值之和分别为 $X$ 和 $Y$，请你找出一种使得 $X$ 与 $Y$ 的差值最小的方案。输出 $X$ 与 $Y$ 的差值。\n\n## Input\n\n第一行包含两个整数 $N$ 和 $M$。\n\n第二行包含 $N$ 个整数，$W_1, W_2, \\cdots, W_N$。\n\n以下 $M$ 行每行包含 $2$ 个整数 $U$ 和 $V$，代表结点 $U$ 和 $V$ 之间有一条边。\n\n## Output\n\n一个整数代表最小的差值。如果不存在合法的删除方案，输出 $-1$。\n\n[samples]\n\n## Note\n\n### 样例说明\n\n由于 $1$ 和 $2$ 之间实际有 $2$ 条边，所以合法的删除方案有 $2$ 种，分别是删除 $(2, 3)$ 之间的边和删除 $(3, 4)$ 之间的边。\n\n删除 $(2, 3)$ 之间的边，剩下的图包含 $2$ 个连通分量：$\\{1,2\\}$ 和 $\\{3,4\\}$，点权和分别是 $30$、$70$，差为 $40$。\n\n删除 $(3, 4)$ 之间的边，剩下的图包含 $2$ 个连通分量：$\\{1,2,3\\}$ 和 $\\{4\\}$，点权和分别是 $60$、$40$，差为 $20$。\n\n### 评测用例规模与约定\n\n - 对于 $20\\%$ 的数据，$1 \\le N, M \\le 10000$。\n - 对于另外 $20\\%$ 的数据，每个结点的度数不超过 $2$。\n - 对于 $100\\%$ 的数据，$1 \\le N, M \\le 200000$，$0 \\le W_i \\le 10^9$，$1 \\le U, V \\le N$。\n \n第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 F 题","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9424","tags":["2023","强连通分量","蓝桥杯国赛"],"sample_group":[["4 4\n10 20 30 40\n1 2\n2 1\n2 3\n4 3","20"]],"created_at":"2026-03-03 11:09:25"}}