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