寒鸽儿のBlog

tarjan缩点后形成一个DAG

然后根据tarjan的性质,缩点的编号为逆拓扑序
直接按缩点编号降序DP即可

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12345, M = 123456;
int head[N<<1], ver[M<<1], my[M<<1], nex[M<<1], tot;
inline void addedge(int u, int v) {
	ver[tot] = v, nex[tot] = head[u], my[tot] = u, head[u] = tot++;
}

int dfn[N], low[N], a[N], sta[N], co[N], sum[N], top, dfs_clock = 1, col = 1;
void tarjan(int cur) {
	dfn[cur] = low[cur] = dfs_clock++;
	sta[top++] = cur;
	for(int i = head[cur]; ~i; i = nex[i])
		if(!dfn[ver[i]]) {
			tarjan(ver[i]);
			low[cur] = min(low[cur], low[ver[i]]);
		} else if(!co[ver[i]]) {
			low[cur] = min(low[cur], dfn[ver[i]]);
		}
	if(dfn[cur] == low[cur]) {
		while(sta[--top] != cur) {
			co[sta[top]] = col;
			sum[col] += a[sta[top]];
		}
		sum[col] += a[cur];
		co[cur] = col++;
	}
} 

int f[N];

int main() {
	memset(head, -1, sizeof(head));
	int n, m, u, v, ans = 0;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i) scanf("%d", a + i);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		addedge(u, v);
	}
	for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
	for(int i = 0, end = tot; i < end; ++i)
		if(co[my[i]] != co[ver[i]])
			addedge(co[my[i]] + n, co[ver[i]]);
	for(int i = col - 1; i; --i) {
		f[i] += sum[i];
		ans = max(f[i], ans);
		for(int j = head[i+n]; ~j; j = nex[j])
			f[ver[j]] = max(f[i], f[ver[j]]);
	}
	printf("%d\n", ans);
	return 0;
}