社区讨论
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 条回复,欢迎继续交流。
正在加载回复...