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; } }
