社区讨论

need help,必回关

P3387【模板】缩点参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m58xpfii
此快照首次捕获于
2024/12/29 09:31
去年
此快照最后确认于
2025/11/04 12:13
4 个月前
查看原帖
思路应该都对,错哪了?
CPP
#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;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...