[洛谷P3627][APIO2009]抢掠计划

题目大意：给你一张$n(n\leqslant5\times10^5)$个点$m(m\leqslant5\times10^5)$条边的有向图，有点权，给你起点和一些可能的终点。问从起点开始，到任意一个终点经过的点权和的最大值是多少。

题解：先把有向图缩点，然后从起点跑最长路，对每个终点取个最大值即可

卡点：求最长路写了$dijkstra$，然后死活调不出。

C++ Code：

#include <algorithm>

#include <cstdio>

#include <cctype>

#include <queue>

namespace __IO {

	int ch;

	inline int read() {

		static int x;

		while (isspace(ch = getchar())) ;

		for (x = ch & 15; isdigit(ch = getchar()); ) x = x * 10 + (ch & 15);

		return x;

	}

}

using __IO::read;

const int maxn = 500010, maxm = 500010;

int n, m;

int w[maxn], W[maxn];

namespace Graph {

	int head[maxn], cnt;

	struct Edge {

		int from, to, nxt;

	} e[maxm];

	inline void addedge(int a, int b) {

		e[++cnt] = (Edge) { a, b, head[a] }; head[a] = cnt;

	}

	int DFN[maxn], low[maxn], idx;

	int S[maxn], top, bel[maxn], scc;

	bool inS[maxn];

	void tarjan(int u) {

		DFN[u] = low[u] = ++idx;

		inS[S[++top] = u] = true;

		int v;

		for (int i = head[u]; i; i = e[i].nxt) {

			v = e[i].to;

			if (!DFN[v]) {

				tarjan(v);

				low[u] = std::min(low[u], low[v]);

			} else if (inS[v]) low[u] = std::min(low[u], DFN[v]);

		}

		if (DFN[u] == low[u]) {

			++scc;

			do {

				inS[v = S[top--]] = false;

				W[bel[v] = scc] += w[v];

			} while (v != u);

		}

	}

}

int head[maxn], cnt;

struct Edge {

	int to, nxt;

} e[maxm];

inline void addedge(int a, int b) {

	e[++cnt] = (Edge) { b, head[a] }; head[a] = cnt;

}

using Graph::scc;

using Graph::bel;

std::queue<int> q;

int dis[maxn];

bool inq[maxn];

void SPFA(int S) {

	dis[S] = W[S];

	q.push(S);

	while (!q.empty()) {

		int u = q.front(); q.pop();

		inq[u] = false;

		for (int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if (dis[v] < dis[u] + W[v]) {

				dis[v] = dis[u] + W[v];

				q.push(v);

				inq[v] = true;

			}

		}

	}

}

int S, ans;

int main() {

	n = read(), m = read();

	for (int i = 0, a, b; i < m; ++i) {

		a = read(), b = read();

		Graph::addedge(a, b);

	}

	for (int i = 1; i <= n; ++i) w[i] = read();

	S = read();

	Graph::tarjan(S);

	for (int i = 1, u, v; i <= m; ++i) {

		u = bel[Graph::e[i].from], v = bel[Graph::e[i].to];

		if (u != v) addedge(u, v);

	}

	SPFA(bel[S]);

	for (int i = read(), x; i; --i) ans = std::max(ans, dis[bel[x = read()]]);

	printf("%d\n", ans);

	return 0;

}