Orz
by Eric_cai @ 2020-12-17 16:39:58
qndmx
by Eric_cai @ 2020-12-17 16:40:12
@[暴力出奇鸡](/user/253433) 我不懂你们为啥开ll啊?
by Marshadow @ 2020-12-17 18:16:40
@[_Reaper_](/user/298325) 本来怀疑是爆int了,所以改了一下,但貌似并没有用
by XeRnHe @ 2020-12-17 18:57:01
@[暴力出奇鸡](/user/253433) 修改后代码如下(修改部分有注释):
``` cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#define reg register
#define MAXN 10005
#define ll long long
using namespace std;
ll n,m,dfsTime,sccCount;
ll pre[MAXN],low[MAXN],sccNo[MAXN],a[MAXN],b[MAXN],in[MAXN],dp[MAXN];
vector<ll> adjtmp[MAXN];
vector<ll> adj[MAXN];
stack<ll> s;
void Tarjan(ll u){
pre[u]=low[u]=++dfsTime;
s.push(u);
for(reg ll i=0;i<adjtmp[u].size();i++){
ll v=adjtmp[u][i];
if(pre[v]==0){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(sccNo[v]==0)
low[u]=min(low[u],pre[v]);
}
if(pre[u]==low[u]){
sccCount++;
while(1){
ll t=s.top();s.pop();
sccNo[t]=sccCount;
b[sccCount]+=a[t];//sccCount 和 u 不一定相等,另开数组求和
if(u==t)
break;
}
}
}
ll topo(){
queue<ll> q;
for(reg ll i=1;i<=sccCount;i++)
if(in[i]==0){
q.push(i);
dp[i]=b[i];
}
while(!q.empty()){
ll u=q.front();q.pop();
for(reg ll i=0;i<adj[u].size();i++){
ll v=adj[u][i];
dp[v]=max(dp[v],dp[u]+b[v]);
in[v]--;
if(in[v]==0)
q.push(v);
}
}
ll ans=0;
for(reg ll i=1;i<=sccCount;i++)
ans=max(ans,dp[i]);
return ans;
}
int main(){
cin>>n>>m;
for(reg ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(reg ll i=1;i<=m;i++){
ll u,v;
scanf("%lld%lld",&u,&v);
adjtmp[u].push_back(v);
}
for(reg ll i=1;i<=n;i++)
if(pre[i]==0)
Tarjan(i);
for(reg ll i=1;i<=n;i++){
for(reg ll j=0;j<adjtmp[i].size();j++){
ll v=adjtmp[i][j];
if(sccNo[i]!=sccNo[v])
adj[sccNo[i]].push_back(sccNo[v]),in[sccNo[v]]++;//sccNo[v] 的入度++,不是 sccNo[i]
}
}
cout<<topo();
return 0;
}
```
by wsyhb @ 2020-12-17 19:11:07
@[wsyhb](/user/145355) 感谢巨佬Orz
by XeRnHe @ 2020-12-17 19:22:18