102674: [AtCoder]ABC267 E - Erasing Vertices 2
Description
Score : $500$ points
Problem Statement
You are given a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects Vertices $U_i$ and $V_i$. Vertex $i$ has a positive integer $A_i$ written on it.
You will repeat the following operation $N$ times.
- Choose a Vertex $x$ that is not removed yet, and remove Vertex $x$ and all edges incident to Vertex $x$. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex $x$ that are not removed yet.
We define the cost of the entire $N$ operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.
Constraints
- $1 \le N \le 2 \times 10^5$
- $0 \le M \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
- $1 \le U_i,V_i \le N$
- The given graph is simple.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$
Output
Print the answer.
Sample Input 1
4 3 3 1 4 2 1 2 1 3 4 1
Sample Output 1
3
By performing the operations as follows, the maximum of the costs of the $N$ operations can be $3$.
- Choose Vertex $3$. The cost is $A_1=3$.
- Choose Vertex $1$. The cost is $A_2+A_4=3$.
- Choose Vertex $2$. The cost is $0$.
- Choose Vertex $4$. The cost is $0$.
The maximum of the costs of the $N$ operations cannot be $2$ or less, so the solution is $3$.
Sample Input 2
7 13 464 661 847 514 74 200 188 5 1 7 1 5 7 4 1 4 5 2 4 5 2 1 3 1 6 3 5 1 2 4 6 2 7
Sample Output 2
1199
Input
题意翻译
有一个有 $n$ 个顶点 $m$ 条边的无向图，每个点有一个点权 $a_i$, 现在你需要进行以下操作 $n$ 次： - 选择一个 **未被删除** 的点 $u$ - 将这个点及其相连的边删除，代价为与它所有 **直接相连** 的 **未被删除的** 的点的点权之和 现在请你求出删除整个无向图，单次操作代价最大值的最小值。 Translated by Microchip2333Output
分数：500分
问题描述
给你一个有N个顶点和M条边的简单无向图。第i条边连接顶点U_i和V_i。顶点i上写有一个正整数A_i。
你将重复执行N次以下操作：
- 选择一个尚未被移除的顶点x，并移除顶点x和所有与顶点x相邻的边。该操作的费用是顶点x直接连接的顶点中尚未被移除的顶点上的整数之和。
我们定义N次操作的总费用为每次操作的费用的最大值。找出总操作的最低可能费用。
约束
- 1≤N≤2×10^5
- 0≤M≤2×10^5
- 1≤A_i≤10^9
- 1≤U_i,V_i≤N
- 给定的图是简单的。
- 输入中的所有值都是整数。
输入
输入格式如下：
N M A_1 A_2 … A_N U_1 V_1 U_2 V_2 ⋮ U_M V_M
输出
打印答案。
样例输入1
4 3 3 1 4 2 1 2 1 3 4 1
样例输出1
3
按照以下方式执行操作，N次操作的最大费用可以为3。
- 选择顶点3。费用为A_1=3。
- 选择顶点1。费用为A_2+A_4=3。
- 选择顶点2。费用为0。
- 选择顶点4。费用为0。
N次操作的最大费用不能为2或更小，所以解决方案为3。
样例输入2
7 13 464 661 847 514 74 200 188 5 1 7 1 5 7 4 1 4 5 2 4 5 2 1 3 1 6 3 5 1 2 4 6 2 7
样例输出2
1199