POJ-3249 : Test for Job
問題概要
ノード数V(<10^5), 辺数E(<10^6)のDAGが与えられる。また、各頂点にコストが割り振られている。sourceからsinkまでのコストがもっとも高いパスを求める問題。
解法
DAGなのでDP。スタックオーバーフローするので再帰は避ける。
acceptされたコード
計算量O(V+E)。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MAX_N = (int)(1e6); const int INF = 0x7fffffff; int N, M; vector<int> graph[MAX_N]; int xs[MAX_N], degs[MAX_N]; int dp[MAX_N]; bool init(){ if(scanf("%d%d", &N, &M)==EOF){ return false; } for(int i=0; i<N; i++){ graph[i].clear(); } for(int i=0; i<N; i++){ scanf("%d", xs+i); } memset(degs, 0, sizeof(degs)); fill(dp, dp + N, -INF); for(int i=0; i<M; i++){ int x, y; scanf("%d%d", &x, &y); x--; y--; graph[x].push_back(y); degs[y]++; } return true; } int solve(){ vector<int> st; for(int i=0; i<N; i++)if(degs[i] == 0){ st.push_back(i); dp[i] = xs[i]; } for(;!st.empty();){ int v = st.back(); st.pop_back(); for(int i=0; i<(int)graph[v].size(); i++){ const int u = graph[v][i]; dp[u] = max(dp[u], dp[v] + xs[u]); if(--degs[u] == 0){ st.push_back(u); } } } int ans = -INF; for(int i=0; i<N; i++)if(graph[i].empty()){ ans = max(ans, dp[i]); } return ans; } int main(){ for(;init();){ printf("%d\n", solve()); } return 0; }