Description Siruseri城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个Siruseri银行的ATM取款机。令人奇怪的是，Siruseri的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。 Banditji计划实施Siruseri有史以来最惊天动地的ATM抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的ATM机，最终他将在一个酒吧庆祝他的胜利。 使用高超的黑客技术，他获知了每个ATM机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个ATM机后，该ATM机里面就不会再有钱了。 例如，假设该城中有6个路口，道路的连接情况如下图所示：
市中心在路口1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中，Banditji能抢劫的现金总数为47，实施的抢劫路线是：1-2-4-1-2-3-5。 Input 第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。 接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。 接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号。 Output 输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。 Sample Input 6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6 Sample Output 47 Hint 50%的输入保证N, M<=3000。 所有的输入保证N, M<=500000。 每个ATM机中可取的钱数为一个非负整数且不超过4000。 输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
本蒟蒻第一眼看到这个题表示被吓到了，APIO的题目！！！肯定巨难。。。 细读题目你会发现这其实是一道Tarjan缩点，跑最长路的大水题！！！ 把环缩成点强行重新建图（变成了DAG），直接暴力SPFA就出来了
空间，常数巨大的代码:
# include <stdio.h> # include <stdlib.h> # include <iostream> # include <string.h> # include <algorithm> # include <queue> using namespace std; # define N 2000001 # define IL inline # define RG register # define UN unsigned # define ll long long # define oo 2147483647 # define mem(a, b) memset(a, b, sizeof(a)) # define max(a, b) ((a) > (b)) ? (a) : (b) # define min(a, b) ((a) < (b)) ? (a) : (b) IL int Get(){ RG char c = '!'; RG int num = 0, z = 1; while(c != '-' && (c > '9' || c < '0')) c = getchar(); if(c == '-') z = -1, c = getchar(); while(c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar(); return num * z; } int n, m, ft[N], nt[N], to[N], bg[N], sk[N], isk[N], dfn[N], low[N], cnt, w[N]; int dis[N], ans, num, cnt1, in[N]; queue <int> Q; IL void Add(RG int u, RG int v){ nt[cnt] = ft[u]; to[cnt] = v; ft[u] = cnt++; } IL void Dfs(RG int u){ low[u] = dfn[u] = ++cnt1; isk[u] = 1; sk[++sk[0]] = u; for(RG int e = ft[u]; e != -1; e = nt[e]){ RG int v = to[e]; if(!dfn[v]){ Dfs(v); low[u] = min(low[v], low[u]); } else if(isk[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]){ RG int v = sk[sk[0]--]; isk[v] = 0; w[++num] += w[v]; bg[v] = num; while(u != v){ v = sk[sk[0]--]; isk[v] = 0; bg[v] = num; w[num] += w[v]; } } } IL void SPFA(RG int s){ in[bg[s]] = 1; Q.push(bg[s]); dis[bg[s]] = w[bg[s]]; while(!Q.empty()){ RG int u = Q.front(); Q.pop(); for(RG int e = ft[u]; e != -1; e = nt[e]){ RG int v = to[e]; if(dis[u] + w[v] > dis[v]){ dis[v] = dis[u] + w[v]; if(!in[v]) in[v] = 1, Q.push(v); } } in[u] = 0; } } int main(){ mem(ft, -1); num = n = Get(); m = Get(); for(RG int i = 1; i <= m; i++){ RG int u = Get(), v = Get(); Add(u, v); } for(RG int i = 1; i <= n; i++) w[i] = Get(); for(RG int i = 1; i <= n; i++) if(!dfn[i]) Dfs(i); for(RG int i = 1; i <= n; i++) for(RG int e = ft[i]; e != -1; e = nt[e]){ RG int v = to[e]; if(bg[i] != bg[v]) Add(bg[i], bg[v]); } SPFA(Get()); RG int t = Get(); while(t--){ RG int bar = Get(); ans = max(ans, dis[bg[bar]]); } printf("%d\n", ans); return 0; }显然我的代码又臭又长，请大佬自行优化
