调了大半天终于调出来了
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
int n, m, cnt, ans;
int a[N], dp[N];
int head[N], to[M], nxt[M];
int head2[N], to2[M], nxt2[M], in[N];
int dfn[N], vis[N], low[N];
int top, sta[N];
int point[N];
void add1(int x, int y)
{
cnt++;
nxt[cnt] = head[x];
to[cnt] = y;
head[x] = cnt;
}
void add2(int x, int y)
{
cnt++;
nxt2[cnt] = head2[x];//注意这里是head2而不是head
to2[cnt] = y;
head2[x] = cnt;
}
void Tarjan(int x)
{
dfn[x] = low[x] = ++cnt;
vis[x] = 1, sta[++top] = x;
for(int i = head[x]; i; i = nxt[i])
{
if(!dfn[to[i]])
{
Tarjan(to[i]);
low[x] = min(low[x], low[to[i]]);
}
else if(vis[to[i]])
{
low[x] = min(low[x], dfn[to[i]]);//如果在栈中要用dfn来更新,不过low好像也行?
}
}
if(low[x] == dfn[x])
{
vis[x] = 0;
point[x] = x;
while(sta[top] != x)
{
int y = sta[top];
vis[y] = 0;
a[x] += a[y];
point[y] = x;
top--;
}
top--;
}
}
void top_sort()
{
queue<int> s;//拓扑排序用栈写...是不是不大合适
for(int i = 1; i <= n; i++)
{
if(i == point[i] && in[i] == 0) s.push(i), dp[i] = a[i];//有点小改动,
}
while(!s.empty())
{
int h = s.front();
s.pop();
for(int i = head2[h]; i; i = nxt2[i])
{
dp[to2[i]] = max(dp[to2[i]], dp[h] + a[to2[i]]);
in[to2[i]]--;
if(!in[to2[i]]) s.push(to2[i]);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
add1(x, y);
}
cnt = 0;
for(int i = 1; i <= n; i++)
{
if(!dfn[i]) Tarjan(i);
}
cnt = 0;
for(int i = 1; i <= n; i++)
{
for(int j = head[i]; j; j = nxt[j])
{
int x = point[i];
int y = point[to[j]];
if(x!=y){//如果位于同一联通分量不要练自环
add2(x, y);
in[y]++;
}
}
}
top_sort();
for(int i = 1; i <= n; i++)
{
ans = max(ans, dp[i]);
}
cout << ans << "\n";
return 0;
}
```
by _zuoqingyuan @ 2023-12-31 22:25:24
@[zhangxiao666](/user/742017) 建议您再看看题解区其他缩点的写法,一般能把代码控制到100行以内。你这个代码看的真难受
by _zuoqingyuan @ 2023-12-31 22:27:47
@[zuoqingyuan](/user/731650) 不好意思,可能是个人码风的问题,十分感谢您的帮助%%%
by zhangxiao666 @ 2023-12-31 22:29:03
@[zuoqingyuan](/user/731650) 已A,感谢,第一次写缩点不太会写,再次感谢您的帮助
by zhangxiao666 @ 2023-12-31 22:31:14