题目链接：
http://poj.org/problem?id=3160
题目大意：
一张有向图，有n个点，m条边，输入“i——j”表示可以从i点走到j点，是单向的。每个点都有权值。
你可以任意选定一个点作为起点，去遍历这个图，当经过一个点的时候，你可以选择取或者不取该点的权值（因为权值有负值）。
求能获得最大权值。
解题思路：
如果是一张有向无环图的话，那么就很简单做树形dp即可。
所以第1步应该是把图化成无环图。
第1步：求强连通分量+缩点，然后建立新图。
第2步：在新图上做树形dp，得到最大的max。
源代码：
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> child[30001];
vector<int> pre[30001];
int v[30001]; //每个点所拥有的权值
int n,m;
int dp[30001]; //用来记录每个点所能获得的最大权值
struct node
{
int id;
int end_time; //结束时间戳
}s[30001];
bool cmp(node a,node b) //按照时间戳进行排序
{
return a.end_time>b.end_time;
}
int vis[30001];
int Set[30001]; //每个点属于的集合
struct node1 //新图的结构体
{
int v;
vector<int> child;
}p[30001];
int Time; //时间戳
int cnt; //强连通分量的个数
int Max; //结果的最大值
void dfs1(int now) //dfs1求取时间戳
{
int i,j,len,kid;
len=child[now].size();
for(i=0;i<len;i++)
{
kid=child[now][i];
if(!vis[kid])
{
vis[kid]=1;
dfs1(kid);
}
}
vis[now]=1;
s[now].id=now;
s[now].end_time=++Time;
return;
}
void dfs2(int now) //dfs2求取强连通分量
{
int i,j,len,father;
len=pre[now].size();
for(i=0;i<len;i++)
{
father=pre[now][i];
if(!vis[father])
{
vis[father]=1;
dfs2(father);
}
}
Set[now]=cnt;
if(v[now]>0)
p[cnt].v+=v[now]; //顺便求取每个强连通点的权值
return;
}
void dfs3(int now) //树形dp求取当前节点能获得的最大价值
{
int i,j,k,len,kid;
len=p[now].child.size();
if(len==0)
{
dp[now]=p[now].v;
return;
}
for(i=0;i<len;i++)
{
kid=p[now].child[i];
if(!vis[kid])
{
vis[kid]=1;
dfs3(kid);
}
dp[now]=max(dp[now],p[now].v+dp[kid]); //当前节点的最大值等于孩子节点的最大值+本身
}
return;
}
int main()
{
freopen("in.txt","r",stdin);
int i,j,k,t,len,a,b,id,x,y;
while(scanf("%d%d",&n,&m)==2)
{
memset(v,0,sizeof(v));
for(i=1;i<=n;i++) //点默认从1开始
scanf("%d",&v[i]);
for(i=0;i<=n;i++)
{
child[i].clear();
pre[i].clear();
}
while(m--)
{
scanf("%d%d",&a,&b);
a++;
b++;
child[a].push_back(b);
pre[b].push_back(a);
}
//进行dfs1求取时间戳
memset(vis,0,sizeof(vis));
Time=0;
for(i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i]=1;
dfs1(i);
}
}
//按照时间戳进行排序
sort(s+1,s+1+n,cmp);
//按照排序后的点，进行第dfs2
memset(vis,0,sizeof(vis));
memset(p,0,sizeof(p));
cnt=0;
for(i=1;i<=n;i++)
{
id=s[i].id;
if(!vis[id])
{
cnt++;
vis[id]=1;
dfs2(id);
}
}
//建立新图
for(i=1;i<=n;i++)
{
x=Set[i];
len=child[i].size();
for(j=0;j<len;j++)
{
y=child[i][j];
y=Set[y];
if(x==y) continue;
p[y].child.push_back(x); //y是x的孩子节点
//p[x].du++; //统计出度
}
}
//对新图进行树形dp
Max=0;
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
for(i=1;i<=cnt;i++)
{
if(!vis[i])
{
vis[i]=1;
dfs3(i);
}
Max=max(dp[i],Max);
}
printf("%d\n",Max);
}
return 0;
}