#include<iostream>
#include<vector>
#include<queue>
#define root 1
using namespace std;
int dfn[10010],low[10010],cnt=0,cl=0,stack[10010],top;
int color[10010];//染色数组
int num[10010];//大小
bool vis[10010];//是否入了栈
int cd[10010];
int mav[10010];//每个强连通分量的值
int f[10010];//状态
int d[10010];
int dis[10010];
inline int min(int x,int y){return ((x<y)?(x):(y));};
inline int max(int x,int y){return ((x>y)?(x):(y));}
vector<int>gra[10010];
vector<int>ngr[10010];
int n,m,ans=0,id=0,s=0;
inline void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
stack[++top]=u,vis[u]=1;
for(int p=0;p<gra[u].size();p++)
{
if(!dfn[gra[u][p]])
{
tarjan(gra[u][p]);
low[u]=min(low[gra[u][p]],low[u]);
}
else
if(vis[gra[u][p]])
low[u]=min(low[u],dfn[gra[u][p]]);
}
if(dfn[u]==low[u])
{
vis[u]=0;
color[u]=++cl;
while(stack[top]!=u)
{
num[cl]++;
mav[cl]+=dis[stack[top]];
cout<<"tarjan up:"<<cl<<' '<<mav[cl]<<endl;
color[stack[top]]=cl;
vis[stack[top--]]=0;
}
top--;
}
}
void dfs(int u)
{
if(f[u])return ;
int maxn=0;
f[u]=mav[u];
for(int p=0;p<ngr[u].size();p++)
{
int v=ngr[u][p];
if(!f[v])dfs(v);
maxn=max(maxn,f[v]);
}
f[u]+=maxn;
}
int main()
{
cin>>n>>m;
for(int p=1;p<=n;p++)
cin>>dis[p];
for(int p=1,x,y;p<=m;p++)
cin>>x>>y,gra[x].push_back(y);
for(int p=1;p<=n;p++)
if(!dfn[p])
tarjan(p);
for(int p=1;p<=n;p++)
{
for(int i=0;i<gra[p].size();i++)
if(color[p]!=color[gra[p][i]])
cd[color[p]]++,ngr[color[p]].push_back(color[gra[p][i]]),d[color[gra[p][i]]]++;
}
for(int p=1;p<=cl;p++)
if(!f[p])
dfs(p);
for(int p=1;p<=cl;p++)
cout<<mav[p]<<' ';
cout<<endl;
for(int p=1;p<=cl;p++)
ans=max(f[p],ans);
cout<<ans<<endl;
}
调试发现mav数组的值不对,然而鹅我的tarjan应该是对的啊/kk
有些东西是调试的,忽略就好
求助/kk
前两次提交都用拓扑的,然而鹅后来因为自己拓扑很烂可能会出错决定换成记忆化搜索……