刚学tarjan的蒟蒻求调!
#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
int n,m,val[N],tpx[N],ans;
int t,top,sum,vis[N],dfn[N],low[N],col[N];
int value[N],rd[N],res;
int f[N];
vector <int> p[N],pp[N],fpp[N];
queue <int> q;
int stac[N];
void tarjan(int u)
{
dfn[u] = ++t;
low[u] = t;
stac[++top] = u;
vis[u] = 1;
for(int i = 0;i < p[u].size();i ++)
{
int v = p[u][i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else
{
if(vis[v])
low[u] = min(low[u],low[v]);
}
}
if(low[u] == dfn[u])
{
col[u] = ++sum;
vis[u] = 0;
while(stac[top] != u)
{
//col[stack[top]] = sum;
value[sum] += val[stac[top]];
col[stac[top]] = sum;
top --;
}
value[sum] += val[stac[top]];
top --;
}
}
void topu()
{
for(int i = 1;i <= sum;i ++)
if(!rd[i])q.push(i);
while(!q.empty())
{
int u = q.front();
tpx[++res] = u;
q.pop();
for(int i = 0;i < pp[u].size();i ++)
{
int v = pp[u][i];
rd[v] --;
if(!rd[v])q.push(v);
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i ++)
cin>>val[i];
for(int i = 1;i <= m;i ++)
{
int a,b;
cin>>a>>b;
p[a].push_back(b);
}
for(int i = 1;i <= n;i ++)
if(!dfn[i])tarjan(i);
for(int u = 1;u <= n;u ++)
for(int i = 0;i < p[u].size();i ++)
{
int v = p[u][i],uu = col[u],vv = col[v];
if(uu != vv)
{
pp[uu].push_back(vv);
fpp[vv].push_back(uu);//建反图,dp时可消除后效性。
rd[vv] ++;
}
}
topu();
for(int i = 1;i <= sum;i ++)
{
int v = tpx[i];
f[v] = value[v];
for(int j = 0;j < fpp[i].size();j ++)
f[v] = max(f[v],f[fpp[v][j]] + value[v]);
}
for(int i = 1;i <= sum;i ++)
ans = max(ans,f[i]);
cout<<ans<<'\n';
return 0;
}
除了AC的全部RE。求大佬帮调!