可以给两个关注qwq
by dpACerLZJun @ 2023-08-12 13:48:20
@[dpACerLZJun](/user/549846) 调出来了
```
# include<iostream>
# include<algorithm>
# include<cmath>
# include<iomanip>
# include<stack>
# include<queue>
# define endl "\n"
using namespace std;
const int maxn=10001, maxm=200001;
struct Node{
int u, v, next;
}edge[maxm], new_edge[maxm];
int n, m, a[maxn], cnt=0, new_cnt=0, head[maxn], new_head[maxn];
int dfn[maxn], low[maxn], vis[maxn], color[maxn], tim=0;
stack<int> s; queue<int> q;
int in_new_edge[maxn], dp[maxn], in[maxn], ans=-1;
void add(int u, int v) {
cnt++;
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void new_add(int u, int v) {
new_cnt++;
new_edge[new_cnt].u=u;
new_edge[new_cnt].v=v;
new_edge[new_cnt].next=new_head[u];
new_head[u]=new_cnt;
in[v]++;
}
void tarjan(int u) {
tim++; dfn[u]=low[u]=tim;
s.push(u); vis[u]=true;
for(int i=head[u]; i; i=edge[i].next) {
int v=edge[i].v;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[v], low[u]);
} else if(vis[v]) low[u]=min(low[u], dfn[v]);
}
if(dfn[u]==low[u]) { // 强连通分量
while(true) {
int t=s.top();
s.pop();
vis[t]=0;
color[t]=u;
if(u==t) break;
else a[u]+=a[t];
}
}
}
int main(){
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=m; i++) {
int u, v; cin >> u >> v;
add(u, v);
}
for(int i=1; i<=n; i++)
color[i]=i;
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);
for(int i=1; i<=m; i++) {
int u=color[edge[i].u], v=color[edge[i].v];
if(u!=v) new_add(u, v);
}
for(int i=1; i<=n; i++)
in_new_edge[color[i]]=true;
// 拓扑dp
for(int i=1; i<=n; i++) {
if(in[i]==0 && in_new_edge[i]) {
q.push(i);
dp[i]=a[i];
}
}
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=new_head[u]; i; i=new_edge[i].next) {
int v=new_edge[i].v;
dp[v]=max(dp[v], dp[u]+a[v]);
in[v]--;
if(in[v]==0) q.push(v);
}
}
for(int i=1; i<=n; i++)
if(in_new_edge[i])
ans=max(ans, dp[i]);
cout << ans << endl;
return 0;
}
```
by Limie @ 2023-08-14 19:16:28
谢大佬，已AC，已关
by dpACerLZJun @ 2023-08-15 11:25:58