No.1911 Alternately Coloring
タグ : / 解いたユーザー数 23
作問者 :
hamamu
Problem Statement
There is a simple connected undirected graph with $N$ vertices and $M$ edges. The $i\ (1\le i \le M)$-th edge connects vertices $u_i,\ v_i$.
Initially, none of the $N$ vertices are colored. chinerist is going to paint each vertex red or blue in the following way.
First, he chooses any vertex, paints it either red or blue as he likes, and places a piece on it.
Next, he performs the following operation $0$ or more times.
Operation- Let $i$ be the vertex on which the piece is currently placed. Choose $1$ vertex $j$ connected to vertex $i$ by an edge. Paint vertex $j$ with the color, out of red and blue, that differs from the color of vertex $i$ (if it is already colored, the color is overwritten), and move the piece to vertex $j$.
After he finishes the operations, for each vertex $i\ (1 \le i \le N)$, he gains $R_i$ points if it is painted red, $B_i$ points if it is painted blue, and $0$ points if it is not colored.
Find the maximum number of points he can obtain after finishing the operations, when he performs them appropriately.
Input
$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $R_1$ $R_2$ $\dots$ $R_N$ $B_1$ $B_2$ $\dots$ $B_N$
- $2 \le N \le 1000$
- $N-1 \le M \le \min(\frac{N(N-1)}{2},1000)$
- $1 \le u_i < v_i \le N$
- $1 \le R_i,\ B_i \le 10^9$
- All input values are integers.
- The given graph is a simple connected undirected graph.
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
3 3 1 2 2 3 1 3 1 2 3 4 3 5
Output
11
If he places the piece on vertex $1$, paints vertex $1$ blue, and then moves the piece in the order vertex $1\rightarrow$ vertex $2\rightarrow$ vertex $3$, vertices $1,\ 2,\ 3$ can be painted blue, red, and blue, respectively. In this case, $4+2+5=11$ points are obtained.
Sample 2
Input
15 20 2 14 1 12 10 11 9 12 4 12 3 8 7 11 1 2 11 14 7 9 14 15 2 6 6 10 3 4 10 13 9 15 5 15 5 8 5 13 3 6 77 109 121 121 163 117 125 149 82 136 81 130 125 102 106 166 39 46 43 69 63 51 57 5 38 14 33 71 29 35
Output
1712
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。