\nhttp:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1179<\/p>\n
\u5f3a\u8054\u901a\u7f29\u70b9\uff0cDAG DP<\/p>\n
\r\nconst int N = int(5e5) + 9;\r\nVI _adj[N], adj[N]; int _bonus[N], bonus[N];\r\nbool _isBar[N], isBar[N];\r\nint _n, n;\r\nint _st;\r\n\r\n\r\nint dfn[N], low[N], bel[N], sta[N], Time, top; VI con[N];\r\n\r\n#define v (*it)\r\nvoid tarjan(int u){\r\n \r\n low[u] = dfn[u] = ++Time;\r\n sta[top++] = u;\r\n \r\n ECH(it, _adj[u]){\r\n if (dfn[v] < dfn[u]){\r\n if (!dfn[v]) tarjan(v);\r\n checkMin(low[u], low[v]);\r\n }\r\n }\r\n \r\n if (low[u] == dfn[u]){\r\n int t;\r\n do{\r\n t = sta[--top];\r\n con[n].PB(t);\r\n bel[t] = n;\r\n dfn[t] = INF;\r\n bonus[n] += _bonus[t];\r\n isBar[n] |= _isBar[t];\r\n } while(t != u);\r\n ++n;\r\n }\r\n}\r\n\r\n\r\nvoid scc(){\r\n \r\n REP_1(u, _n) if(!dfn[u]) tarjan(u);\r\n \r\n REP_1(u, _n) ECH(it, _adj[u]){\r\n int a = bel[u], b = bel[v];\r\n if (a == b) continue;\r\n adj[b].PB(a);\r\n }\r\n}\r\n\r\nint F[N]; int f(int u){\r\n int &res = F[u];\r\n if (res == -1){\r\n int t = -INF;\r\n ECH(it, adj[u]) checkMax(t, f(v));\r\n res = t >= 0 ? t + bonus[u] : -INF;\r\n }\r\n return res;\r\n}\r\n\r\nint main(){\r\n \r\n#ifndef ONLINE_JUDGE\r\n freopen("\/users\/xiaodao\/desktop\/Exercise\/in.txt", "r", stdin);\r\n \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n#endif\r\n \r\n RD(_n); Rush{\r\n int a, b; RD(a, b); --a, --b;\r\n _adj[a].PB(b);\r\n }\r\n REP(i, _n) RD(_bonus[i]);\r\n --RD(_st); Rush _isBar[RD()-1] = true;\r\n \r\n scc();\r\n \r\n FLC(F, -1); int st = bel[_st]; F[st] = bonus[st];\r\n int z = 0; REP(i, n) if (isBar[i]) checkMax(z, f(i));\r\n \r\n \/*REP(i, n){\r\n ECH(it, con[i]) cout << v << " ";\r\n cout << bonus[i] << endl;\r\n }*\/\r\n \r\n cout << z << endl;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[22],"tags":[],"class_list":["post-1178","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-j0","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1178"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1178\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}