题意：
给一个有n个节点的有向图，每个节点有一个值，现在要在图中遍历一次，遍历到一个点可以取走该点的值，现在求在一次遍历中能取到的最大和。
思路：
用tarjan算法缩点后直接搜索最大值。
代码：
//poj 3160
//sepNINE
#include <iostream>
#include <stack>
using namespace std;
const int maxN=30024;
const int maxM=150048;
int value[maxN],head[maxN],treeHead[maxN],dfn[maxN],low[maxN],ins[maxN],belong[maxN];
int sum[maxN];
stack<int> s;
struct Edge{int v,next;
}edge[maxM],treeEdge[maxM];
int n,m,e,treeE,t,cnt;void tarjan(int u){dfn[u]=low[u]=++t;s.push(u);ins[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(dfn[v]==0){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v]==1)low[u]=min(low[u],dfn[v]); }int k;if(low[u]==dfn[u]){++cnt;do{k=s.top();s.pop();ins[k]=0; belong[k]=cnt;}while(low[k]!=dfn[k]); } return ;
}int dfs(int u)
{int tot=sum[u];int maxx=0;for(int i=treeHead[u];i!=-1;i=treeEdge[i].next){int v=treeEdge[i].v;maxx=max(maxx,dfs(v));} return tot+maxx;
}int main()
{while(scanf("%d%d",&n,&m)==2){int i;e=treeE=0;memset(head,-1,sizeof(head));memset(treeHead,-1,sizeof(treeHead));memset(dfn,0,sizeof(dfn));memset(ins,0,sizeof(ins));memset(sum,0,sizeof(sum));while(!s.empty()) s.pop();for(i=0;i<n;++i) scanf("%d",&value[i]); while(m--){int a,b;scanf("%d%d",&a,&b);edge[e].v=b;edge[e].next=head[a];head[a]=e++;}t=cnt=0;for(i=0;i<n;++i)if(!dfn[i])tarjan(i);for(i=0;i<n;++i)if(value[i]>0)sum[belong[i]]+=value[i];for(i=0;i<n;++i)for(int j=head[i];j!=-1;j=edge[j].next){int u=belong[i],v=belong[edge[j].v];if(u!=v){treeEdge[treeE].v=v;treeEdge[treeE].next=treeHead[u];treeHead[u]=treeE++;}}int ans=0;for(i=1;i<=cnt;++i)ans=max(ans,dfs(i));printf("%d\n",ans); } return 0;
}