ARC085 - E問題: MUL

昔いろいろ考えたけど、書き忘れた問題
問題: E - MUL

問題

1, 2, ..., Nの番号がついたN個の宝石がある。ここから宝石を壊していくが、番号iの宝石を残すと円得られる。
数字xを選び、xの倍数の番号がついた宝石を壊すという操作を0回以上行う時、最大で得られる円を求める。

解法

この問題はProject Selection Problemとして考えられ、最小カットで解を求められる。

Project Selection Problemについては以下を参考:
Max-flow min-cut theorem - Wikipedia
最小カットを使って「燃やす埋める問題」を解く
tokoharuさんの"LPとグラフと定式化"

フローの始点を, 終点をとし、番号iの宝石の頂点をとする。
各iについての時はコストのの辺をはり、の時はコストのの辺をはる。
また、番号xの宝石を破壊した時、xの倍数全ての宝石を必ず壊さないといけないということを表すために、コストのの辺をはる。

その上でからへの最大流を計算し、
を解として出力する。

この最小カットは具体例を考えた方が、なぜこのように辺を張るのかがわかりやすそうなので、具体例を書いておく。

まず、問題の入力例1を考える。

6
1 2 -6 4 5 3

この場合は以下の図のようにグラフが構築され、最小カットが求まる。

最小カットにより、壊す方と壊さない方の２つのグループに分断される。
この最小カットで求まった流量3は番号6の宝石を壊すことによる損失である。

また、問題の入力例4を考える。

2
-10000 100000

この場合は以下のように最小カットが求まる。

この最小カットでも止まった流量10000は番号1の宝石を壊さないことによる損失である。

今回の最小カットの結果について、以下の解釈でよさそう

• カットした結果、始点Sから到達できるは壊さない宝石、到達できないは壊す宝石
• カットされた辺が獲得円を減少させる原因になったもの
  • カットする辺候補が複数存在する場合は、どこに原因を着地させても結果は変わらない

提出 (Python3): Submission #2451765 - AtCoder Regular Contest 085

N = int(input())
*A, = map(int, input().split())
dinic = Dinic(N+2)

INF = 10**18

su = 0
for x in range(1, N+1):
    a = A[x-1]
    if a > 0:
        su += a
        # コストa の S -> V_x の辺をはる
        dinic.add_edge(0, x+1, a)
    elif a < 0:
        # コスト-a の V_x -> T の辺をはる
        dinic.add_edge(x+1, 1, -a)

# コスト∞ の V_{kx} -> V_x の辺をはる
for x in range(1, N+1):
    for y in range(x+x, N+1, x):
        dinic.add_edge(y+1, x+1, INF)

print(su - dinic.max_flow(0, 1))