Description
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的单向的道路到达其中的至少一个酒吧。
题解
首先tarjan缩点，然后在DAG上做dp即可。
代码：
#include#include #include #include inline int readInt() { int ans = 0, c; while (!isdigit(c = getchar())); do ans = ans * 10 + c - '0'; while (isdigit(c = getchar())); return ans;}const int N = 500050;int pre[N], nxt[N], to[N], cnt = 0;inline void addEdge(int x, int y) { nxt[cnt] = pre[x]; to[pre[x] = cnt++] = y;}int dfn[N], scc[N], scnt = 0, cnt3 = 0;int stack[N], top = 0;int tarjan(int x) { int low = dfn[x] = ++cnt3; stack[top++] = x; for (int i = pre[x]; ~i; i = nxt[i]) if (!dfn[to[i]]) low = std::min(low, tarjan(to[i])); else if (!scc[to[i]]) low = std::min(low, dfn[to[i]]); if (low == dfn[x]) { ++scnt; while (stack[--top] != x) scc[stack[top]] = scnt; scc[stack[top]] = scnt; } return low;}int pre2[N], nxt2[N], to2[N], cnt2 = 0;inline void addEdge2(int x, int y) { nxt2[cnt2] = pre2[x]; to2[pre2[x] = cnt2++] = y;}int v[N], in[N], f[N];bool vis[N], bar[N];int main() { int n, m, x, s; n = readInt(); m = readInt(); memset(pre, -1, sizeof pre); memset(pre2, -1, sizeof pre2); while (m--) { x = readInt(); addEdge(--x, readInt() - 1); } for (int i = 0; i < n; ++i) if (!dfn[i]) tarjan(i); for (int i = 0; i < n; ++i) v[scc[i]] += readInt(); s = scc[readInt() - 1]; m = readInt(); while (m--) bar[scc[readInt() - 1]] = true; for (int x = 0; x < n; ++x) for (int i = pre[x]; ~i; i = nxt[i]) if (scc[x] != scc[to[i]]) addEdge2(scc[x], scc[to[i]]); int *que = stack, head = 0, tail = 0, ans = 0; vis[que[tail++] = s] = 1; while (head != tail) { int x = que[head++]; for (int i = pre2[x]; ~i; i = nxt2[i]) if (!vis[to2[i]]) que[tail++] = to2[i], vis[to2[i]] = 1; } for (int x = 1; x <= scnt; ++x) if (vis[x]) for (int i = pre2[x]; ~i; i = nxt2[i]) ++in[to2[i]]; head = tail = 0; que[tail++] = s; while (head != tail) { int x = que[head++]; f[x] += v[x]; if (bar[x]) ans = std::max(ans, f[x]); for (int i = pre2[x]; ~i; i = nxt2[i]) { f[to2[i]] = std::max(f[to2[i]], f[x]); if (!--in[to2[i]]) que[tail++] = to2[i]; } } return printf("%d\n", ans) & 0;}