need help,必回关
查看原帖
need help,必回关
1047303
OTOI2025楼主2024/12/29 09:30

思路应该都对,错哪了?

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn = 1000005;
int n, m, tot, tim, top;
int p[maxn], head[maxn], sd[maxn], dfn[maxn], low[maxn];
int stac[maxn], vis[maxn];
int h[maxn], in[maxn], dis[maxn];
struct Edge {
	int u, v, next;
} edge[maxn], ed[maxn];

void insert(int u, int v) {
	edge[++tot].u = u;
	edge[tot].v = v;
	edge[tot].next = head[u];
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++tim;
	stac[++top] = u;
	vis[u] = 1;
	for (int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].v;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		int y;
		do {
			y = stac[top--];
			sd[y] = u;
			vis[y] = 0;
			p[u] += p[y];
		} while (y != u);
	}
}

void topo() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (sd[i] == i) {
			dis[i] = p[i];
			q.push(i);
		}
	}
	while (!q.empty()) {
		int k = q.front();
		q.pop();
		for (int i = h[k]; i; i = ed[i].next) {
			int v = ed[i].v;
			dis[v] = max(dis[v], dis[k] + p[v]);
			in[v]--;
			if (in[v] == 0) q.push(v);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dis[i]);
	}
	printf("%d", ans);
}

void input() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		insert(u, v);
	}
}

int main() {
	input();
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	for (int i = 1; i <= m; i++) {
		int x = sd[edge[i].u], y = sd[edge[i].v];
		if (x != y) {
			ed[++tot].next = h[x];
			ed[tot].v = y;
			ed[tot].u = x;
			h[x] = tot;
			in[y]++;
		}
	}
	topo();
	return 0;
}
2024/12/29 09:30
加载中...