tarjan0分求助 就是跑了一套塔尖,建了一个新图,dfs之后除了样例都没过
#include<stdio.h>
#include<vector>
#include<stack>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,cnt=1;
stack<int>stac;
vector<int>nmap[50005];
vector<int>map[50005];
int ans[10005],rasn,num,real;
int low[10005],dfsn[10005],frank,point[10001],value[10001];
bool vis[10005],sta[10005],clor[10001],travel[10001],color[10001],findit;
void dfs(int a){
travel[a]=1;
findit=0;
for(int i=0;i<nmap[a].size();i++){
if(travel[nmap[a][i]]==0){
findit=1;
num+=point[a];
if(num>real){
real=num;
}
dfs(nmap[a][i]);
num-=point[a];
}
}
}
void Tarjan(int a){
vis[a]=1;
low[a]=dfsn[a]=cnt;
cnt++;
stac.push(a);
sta[a]=1;
for(int i=0;i<map[a].size();i++){
int v=map[a][i];
if(vis[v]==0){
Tarjan(v);
low[a]=min(low[a],low[v]) ;
}
else if(sta[v]==1){
low[a]=min(low[a],low[v]);
}
}
if(dfsn[a]==low[a]){
frank++;
while(a!=stac.top()){
sta[stac.top()]=0;
stac.pop();
clor[stac.top()]=frank;
ans[frank]++;
}
clor[stac.top()]=frank;
stac.pop();
sta[a]=0;
ans[frank]++;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&value[i]);
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
map[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if (!vis[i]) Tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=0;j<map[i].size();j++){
if(clor[i]!=clor[map[i][j]])
nmap[clor[i]].push_back(clor[j]);
}
}
for(int i=1;i<=frank;i++){
if(ans[i]>1){
rasn++;
}
}
for(int i=1;i<=n;i++){
point[low[i]]+=value[i];
}
for(int i=1;i<=rasn;i++){
if(travel[i]!=1) dfs(i);
}
printf("%d",real);
return 0;
}