E - Takahashi's Anguish

[hxrxchang]

https://atcoder.jp/contests/abc256/tasks/abc256_e

問題概要

N人の人がいる。 任意の順番にキャンディを配っていくが、人iは自分より先にXiにキャンディが配られたら不満がCi貯まる。 不満を最小限にする配り方を考えて、そのときの不満の合計を求めよ。

解き方

各頂点の出次数が1のグラフをFunctional Graphという。 Functional Graphには、各連結成分につき閉路が1つあるという特徴がある。

各入力例を図式化すると以下になる

入力例1

入力例2

考え方としては、入次数0のノードからグラフを辿っていけば嫌いな人より先にキャンディが貰えて不満を貯めずに済む。 ただ、前述の通りFunctional Graphは各連結成分につき閉路が1つあるので、閉路間にあるノードの中ではどこか１つ不満を貯めてしまうことになる。一番重みの少ない辺を放つノードに犠牲になってもらえばOKなので、閉路を見つけて、重みが最小の辺を見つける。

閉路を見つけるには、unionfindで繋ごうとしたnodeが既に同じグループであったときに検出できる。 その際にグラフを辿って行って重みが最小の辺を見つけることができる。

func solve() {
    n := getInt()
    _x := getInts()
    x := make([]int, n)
    for i := 0; i < n; i++ {
        x[i] = _x[i] - 1
    }
    c := getInts()

    uf := newUnionFind(n)

    ans := 0
    for i := 0; i < n; i++ {
        if uf.isSame(i, x[i]) {
            cost := c[i]
            node := x[i]
            for node != i {
                cost = min(cost, c[node])
                node = x[node]
            }
            ans += cost
        } else {
            uf.unit(i, x[i])
        }
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc256/submissions/54705489