問題一覧 > 通常問題

No.2236 Lights Out On Simple Graph

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 : srjywrdnprktsrjywrdnprkt / テスター : kemunikukemuniku 👑 seekworserseekworser
6 ProblemId : 9253 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-02 23:12:54

問題文

11 から NN までの番号がついた NN 個の頂点と、11 から MM までの番号がついた MM 本の辺からなる連結とは限らない単純無向グラフが与えられます。辺 ii は頂点 aia_i と頂点 bib_i を結んでいます。

また、各頂点は白か黒のいずれかの色で塗られており、頂点 ii の色は cic_i です。ただし、 ci=0c_i=0 は白を、 ci=1c_i=1 は黒を表します。

あなたは以下の操作を 00 回以上何度でも行えます。全ての頂点の色を白にすることができるか判定し、可能な場合は必要な操作回数の最小値を求めてください。

(操作)
1iM1\leq i \leq M を満たす整数 ii を一つ選び、頂点 aia_i と頂点 bib_i の色をそれぞれ反転させる。すなわち、頂点の色が黒ならば白に、白ならば黒に変える。

入力

N MN~M
a1 b1a_1~b_1
\vdots
aM bMa_{M}~b_{M}
c1  cNc_1~\cdots~c_N

入力は全て整数で以下の制約を満たす。

  • 2N402\leq N \leq 40
  • 1Mmin(N(N1)2,40)1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 40\right)
  • 1ai<biN1\leq a_i < b_i \leq N
  • iji \neq j ならば (ai,bi)(aj,bj)(a_i, b_i) \neq (a_j, b_j)
  • cic_i00 または 11

出力

全ての頂点の色を白にするために必要な操作回数の最小値を出力してください。
ただし、何度操作を行なっても全ての頂点の色を白にできないならば-1を出力してください。
最後に改行してください。

サンプル

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

i=i= 11, 22, 55 の順で操作を行います。すると、各頂点の色は (1,1,1,0,1)(0,0,1,0,1)(0,1,0,0,1)(0,0,0,0,0)(1,1,1,0,1)\to(0,0,1,0,1)\to(0,1,0,0,1)\to(0,0,0,0,0) と変化します。 22 回以下の操作では全ての頂点の色を白にできないので 33 が答えです。

サンプル2
入力
3 1
1 2
0 1 1
出力
-1

何度操作を行なっても、全ての頂点の色を白にすることはできません。与えられるグラフは連結であるとは限らないことに注意してください。

サンプル3
入力
7 9
1 2
1 4
2 3
2 4
3 4
4 5
5 6
5 7
6 7
1 0 1 1 0 0 1
出力
4

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