\(Tarjan\) 模板

#include<cstdio>

#include<queue>

#include<iostream>

#define re register

using namespace std;

const int N = 1e4 + 5;

int n, m, a[N], h1[N], h2[N];

struct edge{int nxt, to;}e1[N * 10], e2[N * 10];

inline void add1(int u, int v)

{

	static int tot1 = 0;

	e1[++tot1] = edge{h1[u], v}, h1[u] = tot1;

}

inline void add2(int u, int v)

{

	static int tot2 = 0;

	e2[++tot2] = edge{h2[u], v}, h2[u] = tot2;

}

int dfn[N], low[N], col[N], vis[N], st[N], top, dfc, color;

void tarjan(int x)

{

	dfn[x] = low[x] = ++dfc, st[++top] = x, vis[x] = 1;

	for(re int i = h1[x]; i; i = e1[i].nxt)

	{

		int v = e1[i].to;

		if (!dfn[v]) tarjan(v), low[x] = min(low[x], low[v]);

		else if (vis[v]) low[x] = min(low[x], dfn[v]);

	}

	if (dfn[x] == low[x])

	{

		col[x] = ++color, vis[x] = 0;

		while (st[top] ^ x) col[st[top]] = color, vis[st[top]] = 0, --top;

		--top;

	}

}

queue<int> Q;

int f[N], val[N], in[N];

int topu()

{

	for(re int i = 1; i <= color; i++)

	if (!in[i]) Q.push(i), f[i] = val[i], vis[i] = 1;

	while (!Q.empty())

	{

		int now = Q.front(); Q.pop();

		for(re int i = h2[now]; i; i = e2[i].nxt)

		{

			--in[e2[i].to], f[e2[i].to] = max(f[e2[i].to], f[now] + val[e2[i].to]);

			if (!in[e2[i].to]) Q.push(e2[i].to);

		}

	}

	int res = 0;

	for(re int i = 1; i <= color; i++) res = max(res, f[i]);

	return res;

}

int main()

{

	scanf("%d%d", &n, &m);

	for(re int i = 1; i <= n; i++) scanf("%d", &a[i]);

	for(re int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), add1(u, v);

	for(re int i = 1; i <= n; i++)

	if (!dfn[i]) tarjan(i);

	for(re int i = 1; i <= n; i++)

	{

		val[col[i]] += a[i];

		for(re int j = h1[i]; j; j = e1[j].nxt)

		if (col[i] ^ col[e1[j].to]) add2(col[i], col[e1[j].to]), ++in[col[e1[j].to]];

	}

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

}
巴特西

P3387 缩点

\(Tarjan\) 模板

最新文章

热门文章
