ARC085 E - MUL - ツバサの備忘録

解法

燃やす埋める問題の応用です。
燃やす埋める問題についてはこちらを参考にするといいかと思います。

今回は、燃やす→売る、埋める→売らない、というようにして帰着させます。
s,tという2つの頂点をつくりsから1~nのすべての頂点への有向辺、1~nの頂点からtへの有向辺を張ります。このときの辺の重み(容量)ですが、上のリンクと同様に、損失に注目して決めていきます。
$a_i>0$ の値をすべて足したものを $x$ とします。このx円は無条件にもらえるものとします。
こうしたとき、それぞれの宝石を売る、売らない時の損失は次のようになります。

$a_i>0$ の場合
売るとき：損失 $0$
売らないとき：損失 $a_i$
$a_i \lt0$ の場合
売るとき：損失 $-a_i$
売らないとき：損失 $0$

ということで、sから張る有向辺を売る、tに向かって張る有向辺を売らないパターンだと考え、上記をもとにして辺の重みを決定していきます。
加えて、この問題ではもう一つ条件が存在します。
$i$ 番目の宝石を売らないときには、 $i$ の倍数番目の宝石をすべて割る必要があるので、 $ik(k>0)$ の宝石はすべて売ることができません。
ということで、これを表現するためには、

頂点 $i$ から、 $i$ の倍数についてすべて重み $\infty$ の有向辺を張る

という操作を行えばいいです。こうすることで、sから頂点 $i$ へ向かう辺をカットしたとき( $i$ 番目の宝石は売らないことにしたとき)に、 $ik$ の頂点のいずれかが売るパターンになっていていてもs-tカットにならなくなります(詳しくは先ほどのリンクを見ていただければと思います)。
ということで、下準備となるグラフの作成が完了しました。
今回は損失について考えているので、あとは最小s-tカットを計算すれば、最初の方で求めた $x$ から引くことで答えが求まります。