题目传送门(BZOJ)
>原文链接<

题解 :

一个环里的提款机, 如果抢了一个就可以全抢, 这是显而易见的

所以我们先用Tarjan缩点, SCC点权是其包含的所有点的点权和.

求一次以1为原点的最长路.

从所有输入的酒吧里, 挑一个距离最大的为答案即可

代码 :

#include <cstdio>#include <cstring>#include <stack>#include <iostream>#include <queue>using namespace std;const int N = 510000;int head[N], to[N], nxt[N]; int v[N]; int dfn[N], low[N], pos[N]; int place[N]; int fr[N], ed[N]; int idx, tot; stack<int>s; int ins[N]; int a[N], cnt; int f[N]; int S; int P;void add(int x, int y) { to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt;}void Tarjan(int p) { dfn[p] = low[p] = ++idx; ins[p] = 1; s.push(p); for(int i=head[p];i;i=nxt[i]) { if(!dfn[to[i]]) { Tarjan(to[i]); low[p] = min(low[p], low[to[i]]); } else if(ins[to[i]]) { low[p] = min(low[p], dfn[to[i]]); } } if(low[p] == dfn[p]) { int t = 0; tot++; while(t!=p) { t = s.top();s.pop(); ins[t] = 0; place[t] = tot; v[tot]+=a[t]; } }}int inq[N];void spfa() { queue<int>q; q.push(place[S]); f[place[S]] = v[place[S]]; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u];i;i=nxt[i]) { if(f[to[i]]<f[u]+v[to[i]]) { f[to[i]] = f[u] + v[to[i]]; if(!inq[to[i]]) { inq[to[i]] = 1; q.push(to[i]); } } } }}int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++ ) { scanf("%d%d", &fr[i], &ed[i]); add(fr[i], ed[i]); } for(int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); } scanf("%d%d", &S, &P); for(int i = 1; i <= n; i ++ ) if(!dfn[i]) Tarjan(i); memset(head, 0, sizeof(head)); cnt = 0; for(int i = 1; i <= m; i ++ ) { int f = fr[i], t = ed[i]; if(place[f]!=place[t]) { add(place[f], place[t]); } } spfa(); int ans = 0; for(int i = 1; i <= P; i ++ ) { int x; scanf("%d", &x); ans = max(ans, f[place[x]]); } printf("%d\n", ans);}