题目链接：http://poj.org/problem?id=3249
思路：dp[i]表示到点i的最大收益，初始化为-inf,然后从入度为0点开始bfs就可以了，一开始一直TLE，然后优化了好久才4000ms险过。
之后有写了个dfs记忆化搜索，果然快多了。
bfs AC code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100100
#define MAXM 2002000
#define inf 1<<30 struct Edge{
int v,next;
}edge[MAXM]; int n,m,NE;
int head[MAXN]; void Insert(int u,int v)
{
edge[NE].v=v;
edge[NE].next=head[u];
head[u]=NE++;
} int In_degree[MAXN],Out_degree[MAXN];
int dp[MAXN],value[MAXN];
bool mark[MAXN]; void bfs()
{
queue<int>que;
fill(dp,dp++n,-inf);
memset(mark,false,(n+)*sizeof(bool));
for(int i=;i<=n;i++)if(In_degree[i]==){
mark[i]=true;
dp[i]=value[i];
que.push(i);
}
while(!que.empty()){
int u=que.front();
que.pop();
mark[u]=false;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(dp[u]+value[v]>dp[v]){
dp[v]=dp[u]+value[v];
if(!mark[v]){
mark[v]=true;que.push(v);
}
}
}
}
} int main()
{
int u,v,ans;
while(~scanf("%d%d",&n,&m)){
NE=;
memset(head,-,(n+)*sizeof(int));
memset(In_degree,,(n+)*sizeof(int));
memset(Out_degree,,(n+)*sizeof(int));
for(int i=;i<=n;i++)scanf("%d",&value[i]);
while(m--){
scanf("%d%d",&u,&v);
Insert(v,u);
In_degree[u]++;
Out_degree[v]++;
}
bfs();
ans=-inf;
for(int i=;i<=n;i++){
if(Out_degree[i]==)ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return ;
}
dfs 记忆化 AC code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100100
#define MAXM 2002000
#define inf 1<<30 struct Edge{
int v,next;
}edge[MAXM]; int n,m,NE;
int head[MAXN]; void Insert(int u,int v)
{
edge[NE].v=v;
edge[NE].next=head[u];
head[u]=NE++;
} int In_degree[MAXN],Out_degree[MAXN];
int dp[MAXN],value[MAXN]; int dfs(int u)
{
if(dp[u]!=-inf)return dp[u];
dp[u]=value[u];
int ans=-inf;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
ans=max(ans,dfs(v));
}
if(ans!=-inf){
dp[u]+=ans;
}
return dp[u];
} int main()
{
int u,v,ans;
while(~scanf("%d%d",&n,&m)){
NE=;
memset(head,-,(n+)*sizeof(int));
memset(In_degree,,(n+)*sizeof(int));
memset(Out_degree,,(n+)*sizeof(int));
for(int i=;i<=n;i++)scanf("%d",&value[i]);
while(m--){
scanf("%d%d",&u,&v);
Insert(u,v);
In_degree[v]++;
Out_degree[u]++;
}
ans=-inf;
fill(dp,dp++n,-inf);
for(int i=;i<=n;i++){
if(In_degree[i]==){
ans=max(ans,dfs(i));
}
}
printf("%d\n",ans);
}
return ;
}