No.3781 Erase One, Gain from the Other
タグ : / 解いたユーザー数 17
作問者 :
Problem Statement
There is an undirected graph with $N$ vertices and $M$ edges. The vertices are numbered with integers from $1$ to $N$, and the edges are numbered with integers from $1$ to $M$. For $1\le i \le M$, edge $i$ connects vertex $u_i$ and vertex $v_i$ bidirectionally. Each vertex also has a non-negative integer weight, and for $1\le i\le N$, the weight of vertex $i$ is $A_i$.
Initially, no vertex is painted black. Consider the following operation.
- Choose $1$ pair $(u,v)$ of $2$ vertices such that neither of them is painted black and they are directly connected by an edge. Paint $u$ black and gain $A_v$ yen.
Note that since every edge is undirected, whenever the operation is possible for the pair $(u,v)$, it is also possible for the pair $(v,u)$.
What is the maximum possible total amount of money that can be gained by performing this operation any number of times, $0$ or more?
Solve $T$ test cases.
Constraints
- $1\le T\le 2\times 10^5$
- $1\le N\le 2\times 10^5$
- $0\le M\le 2\times 10^5$
- $1\le u_i < v_i\le N\ (1\le i\le M)$
- $(u_i,v_i) \neq (u_j,v_j)\ (1\le i < j\le M)$
- $0\le A_i\le 10^9\ (1\le i\le N)$
- The sum of $N$ and the sum of $M$ over the $T$ test cases are each at most $2\times 10^5$
- All input values are integers
Input
The input is given in the following format, where $case_i$ represents the $i$-th test case.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each test case is given in the following format.
$N\ M$ $A_1\ A_2\ \cdots\ A_N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$
Output
Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.
Sample
Sample 1
Input
2 6 7 7 2 3 1 3 6 1 2 1 3 2 4 3 4 3 5 4 6 5 6 10 13 4 9 0 6 7 1 5 9 3 7 1 6 1 7 1 9 2 4 2 9 3 7 3 9 5 10 6 7 6 8 6 9 8 9 9 10
Output
26 52
In test case $1$, you can gain $26$ yen by performing the operations as follows.
- Perform the operation on $(2,1)$. You gain $7$ yen.
- Perform the operation on $(3,1)$. You gain $7$ yen.
- Perform the operation on $(4,6)$. You gain $6$ yen.
- Perform the operation on $(5,6)$. You gain $6$ yen.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。