@[愚かなる弟よ](/user/200044) 爆int?
by 闪电皮卡丘 @ 2020-05-04 10:10:32
@[愚かなる弟よ](/user/200044) 额 看来不是
by 闪电皮卡丘 @ 2020-05-04 10:11:54
@[闪电皮卡丘](/user/224112) 试过了,不是
by JS_TZ_ZHR @ 2020-05-04 10:12:00
我再看看,先放个数据
```cpp
10 20
970 369 910 889 470 106 658 659 916 964
3 2
3 6
3 4
9 5
8 3
5 8
9 1
9 7
9 8
7 5
3 7
7 8
1 7
10 2
1 10
4 8
2 6
3 1
3 5
8 5
```
by JK_LOVER @ 2020-05-04 10:12:33
6911
by JK_LOVER @ 2020-05-04 10:12:46
@[JK_LOVER](/user/227824) 早试过了,我输出5947,不知道为什么
by JS_TZ_ZHR @ 2020-05-04 10:14:29
@[愚かなる弟よ](/user/200044)
by JK_LOVER @ 2020-05-04 10:34:42
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,sum[100005],u,v,dfn[100005],cnt,low[100005],total,color[100005],dis[100005];
int in[100005],tp[100005],ans,f[100005],_cnt;
bool vis[100005];
vector<int>ve[100005],from[100005],to[100005];
stack<int>s;
void tarjan(int now) {
dfn[now]=low[now]=++cnt;
s.push(now);
vis[now]=true;
for(int i=0; i<ve[now].size(); i++) {
if(!dfn[ve[now][i]]) {
tarjan(ve[now][i]);
low[now]=min(low[now],low[ve[now][i]]);
} else if(vis[ve[now][i]])
low[now]=min(low[now],dfn[ve[now][i]]);
}
if(low[now]==dfn[now]) {
total++;
while(1) {
int temp=s.top();
color[s.top()]=total;
dis[total]+=sum[s.top()];
vis[s.top()]=false;
s.pop();
if(now==temp)break;
}
}
return;
}
void bfs() {
queue<int>q;
for(int i=1; i<=total; i++)if(!in[i])q.push(i);
while(!q.empty()) {
int y=q.front();
tp[++_cnt]=y;
q.pop();
for(int i=0; i<to[y].size(); i++) {
in[to[y][i]]--;
if(!in[to[y][i]])q.push(to[y][i]);
}
}
return;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)scanf("%d",&sum[i]);
for(int i=1; i<=m; i++) {
scanf("%d%d",&u,&v);
ve[u].push_back(v);
}
for(int i=1; i<=n; i++)if(!dfn[i])tarjan(i);
for(int i=1; i<=n; i++) {
for(int j=0; j<ve[i].size(); j++) {
int x=color[i],y=color[ve[i][j]];
if(x!=y) {
from[y].push_back(x);
to[x].push_back(y);
in[y]++;
}
}
}
for(int i=total; i>=1; i--) {
f[i]=dis[i];
ans=max(ans,f[i]);
for(int j=0; j<from[i].size(); j++) {
f[i]=max(f[i],dis[i]+f[from[i][j]]);
}
}
for(int i=1;i<=total;i++)ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
```
by JK_LOVER @ 2020-05-04 10:35:47
@[愚かなる弟よ](/user/200044)
```cpp
for(int i=1; i<=n; i++) {
for(int j=0; j<ve[i].size(); j++) {
int x=color[i],y=color[ve[i][j]];
if(x!=y) {
from[y].push_back(x);
to[x].push_back(y);
in[y]++;
}
}
}
```
$j$打成$i$了
by JK_LOVER @ 2020-05-04 10:36:39
不会有第5次了/xyx (逃)
by JK_LOVER @ 2020-05-04 10:37:14