| Time Limit: 1000MS | Memory Limit: 131072K | |
| Total Submissions: 3496 | Accepted: 1191 |
缩点，然后每个新点跑一边SPFA
思路不难 ，注意细节~
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue> using namespace std; const int M(+);
const int N(+);
int n,m,u,v,val[N],ans; int hed[N],had[N],sumedge;
struct Edge
{
int v,next;
}edge[M];
void ins(int u,int v,int *head)
{
sumedge++;
edge[sumedge].v=v;
edge[sumedge].next=head[u];
head[u]=sumedge;
} int dfn[N],low[N],tim;
int col[N],sumcol,cval[N];
int Stack[N],instack[N],top;
void DFS(int now)
{
dfn[now]=low[now]=++tim;
Stack[++top]=now,instack[now]=;
for(int i=hed[now];i;i=edge[i].next)
{
int to=edge[i].v;
if(!dfn[to]) DFS(to),low[now]=min(low[now],low[to]);
else if(instack[to]) low[now]=min(low[now],dfn[to]);
}
if(low[now]==dfn[now])
{
col[now]=++sumcol;
cval[sumcol]+=val[now];
for(;Stack[top]!=now;top--)
{
col[Stack[top]]=sumcol;
cval[sumcol]+=val[Stack[top]];
instack[Stack[top]]=;
}
instack[now]=;top--;
}
} int rd[N];
void Get_map()
{
for(u=;u<=n;u++)
for(int i=hed[u];i;i=edge[i].next)
{
v=edge[i].v;
if(col[u]!=col[v])
rd[col[v]]++,ins(col[u],col[v],had);
}
} queue<int>que;
int inq[N],dis[N];
int SPFA(int s)
{
int ret=dis[s]=cval[s];
memset(inq,,sizeof(inq));
que.push(s);inq[s]=;
while(!que.empty())
{
u=que.front();que.pop(),inq[u]=;
for(int i=had[u];i;i=edge[i].next)
{
v=edge[i].v;
if(dis[v]<dis[u]+cval[v])
{
dis[v]=dis[u]+cval[v];
ret=max(ret,dis[v]);
if(!inq[v])
que.push(v),inq[v]=;
}
}
}
return ret;
} void init()
{
sumcol=sumedge=top=tim=ans=;
memset(rd,,sizeof(rd));
memset(hed,,sizeof(hed));
memset(had,,sizeof(had));
memset(dis,,sizeof(dis));
memset(col,,sizeof(col));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(val,,sizeof(val));
memset(cval,,sizeof(cval));
memset(Stack,,sizeof(Stack));
memset(instack,,sizeof(instack));
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=;i<=n;i++)
scanf("%d",val+i),val[i]=max(,val[i]);
for(int u,v;m--;)
scanf("%d%d",&u,&v),ins(u+,v+,hed);
for(int i=;i<=n;i++) if(!dfn[i]) DFS(i);
Get_map();
for(int i=;i<=sumcol;i++)
if(!rd[i]) ans=max(ans,SPFA(i));
printf("%d\n",ans);
}
return ;
}