首页 > 代码库 > POJ 3249 Test for Job (dfs + dp)
POJ 3249 Test for Job (dfs + dp)
题目链接:http://poj.org/problem?id=3249
题意:
给你一个DAG图,问你入度为0的点到出度为0的点的最长路是多少
思路:
记忆化搜索,注意v[i]可以是负的,所以初始值要-inf。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int N = 1e5 + 5; 6 typedef long long LL; 7 struct Edge { 8 int next, to; 9 }edge[N * 10];10 LL dp[N], a[N], inf = 1e12;11 int head[N], tot, input[N];12 13 void init(int n) {14 for(int i = 1; i <= n; ++i) {15 head[i] = -1;16 dp[i] = -inf;17 input[i] = 0;18 }19 tot = 0;20 }21 22 inline void add(int u, int v) {23 edge[tot].next = head[u];24 edge[tot].to = v;25 head[u] = tot++;26 }27 28 void dfs(int u) {29 if(dp[u] != -inf)30 return ;31 for(int i = head[u]; ~i; i = edge[i].next) {32 int v = edge[i].to;33 dfs(v);34 dp[u] = max(dp[v] + a[u], dp[u]);35 }36 if(dp[u] == -inf) //若是出度为037 dp[u] = a[u];38 }39 40 int main()41 {42 int n, m;43 while(~scanf("%d %d", &n, &m)) {44 for(int i = 1; i <= n; ++i) {45 scanf("%lld", a + i);46 }47 init(n);48 int u, v;49 for(int i = 1; i <= m; ++i) {50 scanf("%d %d", &u, &v);51 add(u, v);52 input[v]++;53 }54 LL Max = -inf;55 for(int i = 1; i <= n; ++i) {56 if(!input[i]) {57 dfs(i);58 Max = max(Max, dp[i]);59 }60 }61 printf("%lld\n", Max);62 }63 return 0;64 }
POJ 3249 Test for Job (dfs + dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。