em……没用到拓扑,就是将点合并,链接的边聚到一起,求大佬debug(下有注释说明)
#include<bits/stdc++.h>
#define N 10010
using namespace std;
int n,a,b,m,dfn[N],low[N],cnt;
int stk[N],top,s[N],to[N];
int d[N],dp[N];
bool in[N];
int ans;
vector <int> e[N],l[N];
void tarjan(int x)//tarjan
{
stk[++ top] = x;
dfn[x] = low[x] = ++ cnt;
in[x] = 1;
for(int i = 0;i < e[x].size();i ++)
{
int v = e[x][i];
if(!dfn[v])
{
tarjan(v);
low[x] = min(low[x],low[v]);
}
else if(in[v]) low[x] = min(low[x],low[v]);
}
if(dfn[x] == low[x])//强联通->缩点(预备)
{
while(stk[top] != x)
{
in[stk[top]] = 0;
s[x] += s[stk[top]];//缩到一个点
to[stk[top]] = x;//指向缩的点
top --;
}
to[x] = x;//自己指自己
in[x] = 0;
top --;
}
return;
}
void dfs(int x,int fa)
{
dp[x] = max(dp[x],dp[fa] + s[x]);//dp
for(int i = 0;i < l[x].size();i ++) dfs(l[x][i],x);//看儿子
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> s[i];
for(int i = 1;i <= m;i ++)
{
cin >> a >> b;
e[a].push_back(b);
}
for(int i = 1;i <= n;i ++)
{
if(!dfn[i]) tarjan(i);
}
for(int i = 1;i <= n;i ++)
{
int v = to[i];//指向缩的点
for(int j = 0;j < e[i].size();j ++)//将边给缩点代表
{
int u = e[i][j];
if(to[u] != v) l[v].push_back(u),d[u] ++;//合并边
}
}
for(int i = 1;i <= n;i ++)//dp,从入度为0的开始找(d[i])
{
if(!d[i]) dfs(i,0);
ans = max(ans,dp[i]);//去最大dp值
}
cout << ans << endl;
return 0;
}