【精進9】ARC030-C 有向グラフ

結構面倒だった

問題概要

C - 有向グラフ
$N$頂点$M$辺の有向グラフが与えられる。各頂点には英小文字が書かれている。好きな頂点から開始し、英小文字を回収するか選び移動することを繰り返すとき長さ$K$の得られる文字列の内、辞書順最小のものを求めよ。

解法

強連結な集合内は自由に行き来できるから、文字を小さい順に貪欲に回収できる。従って強連結成分分解することで各頂点に(文字ではなく)文字列が書かれたDAGの問題に帰着できる。各頂点には元のグラフの強連結成分の頂点に書かれた文字をソートして並べた文字列が書かれているとする。$\mathrm{DP}[i][j]$ : 「頂点$i$及びより上流(用語がわからない)の頂点を使ってできる長さ$j$の文字列の内、辞書順最小のもの」としてDPをすれば解ける。
ところでchminを文字列で初めて使ったかもしれない。

#include "template.hpp"
#include "data_structure/hash-map-variable-length.hpp"
#include <atcoder/scc>
void solve() {
    LL(n, m, k);
    vector<char> c(n);
    input(c);
    atcoder::scc_graph g(n);
    vector<P> edge(m);
    rep(i, m) {
        LL(a, b);
        g.add_edge(--a, --b);
        edge[i] = {a, b};
    }
    auto scc = g.scc();
    ll sz = scc.size();
    HashMap<ll> mp;
    vector<string> s(sz);
    rep(i, sz) {
        for(auto &j : scc[i]) {
            mp[j] = i;
            s[i].push_back(c[j]);
        }
    }
    Graph gs(sz);
    for(const auto &[i, j] : edge) {
        if(mp[j] != mp[i])
            gs[mp[j]].push_back(mp[i]);
    }
    rep(i, sz) {
        sort(all(gs[i]));
        gs[i].erase(unique(all(gs[i])), end(gs[i]));
        sort(all(s[i]));
    }
    vector<vector<string>> dp;
    string ans;
    char z = '{';
    {
        ans = string(k, z);
        vector<string> dp0(k + 1);
        rep(i, k + 1) {
            dp0[i] = string(i, z);
        }
        dp.resize(sz, dp0);
    }
    rep(i, sz) {
        vector<string> pdp(k + 1);
        rep(j, k + 1) pdp[j] = string(j, z);
        for(auto prev : gs[i]) {
            rep(j, k + 1) {
                chmin(pdp[j], dp[prev][j]);
            }
        }
        auto &str = s[i];
        rep(j, k + 1) {
            rep(l, min(j, ssize(str)) + 1) {
                chmin(dp[i][j], pdp[j - l] + str.substr(0, l));
            }
        }
        chmin(ans, dp[i][k]);
    }
    if(ans[0] == z) {
        print(-1);
    } else
        print(ans);
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    rep(_, t) {
        solve();
    }
}