問題一覧 > 通常問題

No.1911 Alternately Coloring

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : chineristACchineristAC / テスター : hamamuhamamu tokusakuraitokusakurai
4 ProblemId : 7294 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-12 23:28:53

問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフがあります。 $i\ (1\le i \le M)$ 番目の辺は頂点 $u_i,\ v_i$ を結びます。

$N$ 個の頂点ははじめ、色が塗られていません。chinerist 君はこれから以下のようにして各頂点を赤色、または青色で塗ることにしました。

まずはじめに好きな頂点を選び、頂点を赤色、青色のうち好きな方で塗り、駒を置きます。

つぎに以下のような操作を $0$ 回以上行います。

操作
  • 現在駒が置かれている頂点を $i$ とする。頂点 $i$ と辺で結ばれているような頂点 $j$ を $1$ つ選ぶ。頂点 $j$ を赤色、青色のうち、頂点 $i$ の色とは異なる色で塗り(すでに色が塗られている場合は上書きする)、駒を頂点 $j$ に移動する。

操作を終えた後、各頂点 $i\ (1 \le i \le N)$ について、赤色が塗られていた場合 $R_i$ 点、青色が塗られていた場合 $B_i$ 点、色が塗られていない場合は $0$ 点を得ることができます。

chinerist 君が適切に操作を行った場合、操作を終えた後最大で何点得られるか求めてください。

入力

$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$
  • 与えられる入力はすべて整数
  • 与えられるグラフは単純連結無向グラフ

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3
1 2
2 3
1 3
1 2 3
4 3 5
出力
11

駒を頂点 $1$ に置き、頂点 $1$ を青色に塗った後、頂点 $1\rightarrow$ 頂点 $2\rightarrow$ 頂点 $3$ の順に駒を動かすと、頂点 $1,\ 2,\ 3$ を青、赤、青色で塗ることができます。この場合は $4+2+5=11$ 点が得られます。

サンプル2
入力
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
出力
1712

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。