AOJ 2598 Website Tour

解法

移動に時間がかからないので,各強連結成分においては,好きな広告を(制限以内なら)好きな回数だけ見ることが出来ます.これは典型的な個数制限付きナップザック問題です.

あとは強連結成分分解をしたグラフで,トポロジカル順序でDP(DAGの上のDP)をします.
各強連結成分では,先に述べた個数制限付きナップザック問題を解きますが,自己辺が無いようなそれ自身だけからなる強連結成分は,自分の広告を何回も見ることはどうやっても出来ないので,個数制限を 1 と改めておきます.
あとは普通のナップザック問題で,
$dp[i][j] := $ 頂点 $i$ まで見たときに,時間の総和が $j$ 以下であるような広告の見方をしたときの最大値
として,各頂点で答えが求まったら,子に対して $dp[child][j] = dp[i][j]$ とかするだけでよいです.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

struct edge {
    int from, to;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to) {
    g[from].push_back((edge){from, to});
}

int scc(graph& G, std::vector<int>& cmp) {
    int V = G.size();
    std::vector<std::vector<int>> g(V), rg(V);
    std::vector<bool> used(V, false);
    std::vector<int> vs;
    cmp.resize(V);
    for(int i=0; i<V; ++i) {
        for(auto e : G[i]) {
            g[i].push_back(e.to);
            rg[e.to].push_back(i);
        }
    }
    std::function<void(int)> dfs = [&g, &vs, &used, &dfs](int v) {
        used[v] = true;
        for(auto i : g[v]) {
            if(!used[i]) {
                dfs(i);
            }
        }
        vs.push_back(v);
    };
    std::function<void(int, int)> rdfs = [&rg, &cmp, &used, &rdfs](int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for(int i : rg[v]) {
            if(!used[i]) {
                rdfs(i, k);
            }
        }
    };
    for(int v=0; v<V; ++v) {
        if(!used[v]) {
            dfs(v);
        }
    }
    std::fill(used.begin(), used.end(), false);
    int k = 0;
    for(int i=vs.size()-1; i>=0; --i) {
        if(!used[vs[i]]) {
            rdfs(vs[i], k++);
        }
    }
    return k;
}

std::vector<std::vector<int>> build_graph(graph const& g, std::vector<int> const& cmp, int K) {
    int V = g.size();
    std::vector<std::set<int>> s(K);
    std::vector<std::vector<int>> res(K);
    for(int i=0; i<V; ++i) {
        for(auto e : g[i]) {
            s[cmp[i]].insert(cmp[e.to]);
        }
    }
    for(int i=0; i<K; ++i) {
        for(auto j : s[i]) {
            if(i != j) {
                res[i].push_back(j);
            }
        }
    }
    return res;
}


int main() {
    int N, M, T;
    while(cin >> N >> M >> T, N) {
        graph g(N);
        vector<int> p(N), t(N), k(N);
        vector<bool> self(N);
        for(int i = 0; i < N; ++i) {
            cin >> p[i] >> t[i] >> k[i];
        }
        for(int i = 0; i < M; ++i) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            add_edge(g, a, b);
            if(a == b) {
                self[a] = true;
            }
        }
        
        vector<int> cmp;
        int const K = scc(g, cmp);
        auto g2 = build_graph(g, cmp, K);
        vector<vector<int>> C(K);
        for(int i = 0; i < N; ++i) {
            C[cmp[i]].push_back(i);
        }

        vector<vector<int>> dp(K, vector<int>(T + 1));
        for(int i = 0; i < K; ++i) {
            if(C[i].size() == 1 && !self[C[i][0]]) {
                k[C[i][0]] = 1;
            }
            for(auto v : C[i]) {
                for(int j = 0; j < t[v]; ++j) {
                    deque<pii> deq;
                    for(int l = 0; l * t[v] + j <= T; ++l) {
                        int val = dp[i][l * t[v] + j] - l * p[v];
                        while(deq.size() > 0 && deq.back().second <= val) {
                            deq.pop_back();
                        }
                        deq.emplace_back(l, val);
                        dp[i][l * t[v] + j] = deq.front().second + l * p[v];
                        if(deq.front().first == l - k[v]) {
                            deq.pop_front();
                        }
                    }
                }
                for(auto to : g2[i]) {
                    for(int j = 0; j <= T; ++j) {
                        dp[to][j] = max(dp[to][j], dp[i][j]);
                    }
                }
            }
        }

        int res = 0;
        for(int i = 0; i < K; ++i) {
            res = max(res, dp[i][T]);
        }
        cout << res << endl;
    }
}

感想

最初何を血迷ったか,DFSしながら各連結成分ごとに dp2[i][j] を計算し,dp[i][j] = max(dp[ch][j - t], dp2[i][t]) みたいに実装しようとしていて O(nT^2) でだめだなーとかアホな事を考えていた.