DAG上の最長経路

[tipstar0125]

https://atcoder.jp/contests/abc335/tasks/abc335_e

• DAG: 有向非巡回グラフ
• DAG上の最長経路は上流からdp

[tipstar0125]

input! {
    N: usize,
    M: usize,
    A: [usize; N],
    UV: [(Usize1, Usize1); M]
}

let mut vp = vec![vec![]; 2e5 as usize + 1];
let mut uf = UnionFind::new(N);
for &(mut u, mut v) in &UV {
    if A[u] > A[v] {
        std::mem::swap(&mut u, &mut v);
    }
    if A[u] == A[v] {
        uf.unite(u, v);
    } else {
        vp[A[u]].push((u, v));
    }
}
let INF = 1_isize << 60;
let mut dp = vec![-INF; N];
dp[uf.find(0)] = 1;
for uv in vp.iter() {
    for &(mut u, mut v) in uv.iter() {
        u = uf.find(u);
        v = uf.find(v);
        dp[v] = max!(dp[v], dp[u] + 1);
    }
}
println!("{}", max!(0, dp[uf.find(N - 1)]));

[tipstar0125]

ダイクストラによる解法 参考：https://atcoder.jp/contests/abc335/editorial/9054

• 未確定の頂点 v のうち A[v] が最も小さく、その中でスコアが最大の頂点のスコアを確定する
• 辺u-v、A[u]<A[v]のとき遷移はu->vのみで、u<-vの遷移はないので、小さい方から確定していけばよい

input! {
    N: usize,
    M: usize,
    A: [usize; N],
    UV: [(Usize1, Usize1); M]
}

let mut G = vec![vec![]; N];
for &(mut u, mut v) in UV.iter() {
    if A[u] > A[v] {
        std::mem::swap(&mut u, &mut v);
    }
    if A[u] == A[v] {
        G[u].push((v, 0));
        G[v].push((u, 0));
    } else {
        G[u].push((v, 1));
    }
}
let mut score = vec![0; N];
let mut Q = BinaryHeap::new();
score[0] = 1;
Q.push((Reverse((A[0], -score[0])), 0));
while let Some((Reverse((_, s)), pos)) = Q.pop() {
    if score[pos] != -s {
        continue;
    }
    for &(next, ns) in &G[pos] {
        if score[pos] + ns > score[next] {
            score[next] = score[pos] + ns;
            Q.push((Reverse((A[next], -score[next])), next));
        }
    }
}
println!("{}", score[N - 1]);