燃やす埋める練習問題2

2 secs 1024 MB
_kanpurin_'s icon _kanpurin_

問題文

頂点数L,R|L|,|R|、辺数MMの二部グラフおよび各頂点の重みwLi,wRiw_{L_i},w_{R_i}が与えられます。jj番目の辺は頂点LxjL_{x_j}と頂点RyjR_{y_j}を結んでいます。このグラフにおける最大重み独立集合を求め、重みの和を出力してください。

最大重み独立集合とは独立集合のうち、頂点の重みの和が最大となるもののことです。

制約

  • 1L,R1001 \leq |L|,|R| \leq 100
  • 0ML×R0 \leq M \leq L\times R
  • 1wLi,wRi1091\leq w_{L_i},w_{R_i} \leq 10^9
  • 1xjL1\leq x_j\leq L
  • 1yjR1\leq y_j\leq R
  • ij(xi,yi)(xj,yj)i\neq j \Leftrightarrow (x_i,y_i)\neq (x_j,y_j)

入力

入力はすべて整数である。

L R M|L|\ |R|\ M
wL1 wL2  wLLw_{L_1}\ w_{L_2}\ \dots\ w_{L_L}
wR1 wR2  wRLw_{R_1}\ w_{R_2}\ \dots\ w_{R_L}
x1 y1x_1\ y_1
x2 y2x_2\ y_2
\vdots
xM yMx_M\ y_M

出力

計算結果を一行に出力せよ。

サンプル

入力1
3 3 4
1 1 1
1 1 1
1 1
2 2
2 3
3 1
出力1
4

重みがすべて11なので最大独立集合の大きさと一致します。{L1,L3,R2,R3}\{L_1,L_3,R_2,R_3\}が重み最大となります。

入力2
3 3 4
1 3 1
3 1 1
1 1
2 2
2 3
3 1
出力2
6

グラフはサンプル11と同じですが重みが異なります。独立集合の大きさが最大である必要はありません。{L2,R1}\{L_2,R_1\}が重み最大となります。

提出


Go (1.21)