感觉和NOIP2009提高组第3题差不多，要强连通缩点，我用的是Tarjan算法，以前看不懂，现在才理解了。
然后再动态规划。
还有，就是数据很变态，单纯的递归过不了，要将之非递归化。
CO
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-4-18
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#define MAXN 500000
#define MAXM 500000
#define MIN(a,b) ((a)<(b)?(a):(b))
struct Link{Link* next;int to;};
int N,M;
Link* link[MAXN];
int money[MAXN];
int S,P;
bool isBar[MAXN];
int belong[MAXN];
void insert(int,int);
void tarjan(int);
int DP(int);
int main()
{
//freopen(“atm.in”,”r”,stdin);
//freopen(“atm.out”,”w”,stdout);
scanf(“%d %d\n”,&N,&M);
for (int i=0;i<M;i++)
{
int u,v;
scanf(“%d %d\n”,&u,&v);
insert(u-1,v-1);
}
for (int i=0;i<N;i++)
scanf(“%d\n”,&money[i]);
scanf(“%d %d\n”,&S,&P);
for (int i=0;i<P;i++)
{
int pos;
if (i+1!=P) scanf(“%d “,&pos);
else scanf(“%d\n”,&pos);
isBar[pos-1]=true;
}
/*
for (int root=0;root<N;root++)
{
printf(“%d:”,root+1);
for (Link* i=link[root];i!=0;i=i->next)
printf(“%d “,i->to+1);
printf(“\n”);
}
*/
tarjan(S-1);
/*
for (int i=0;i<N;i++)
if (belong[i]==i)
printf(“%d %d %d\n”,i+1,isBar[i],money[i]);
*/
printf(“%d\n”,DP(S-1));
//fclose(stdin);
//fclose(stdout);
return 0;
}
void insert(int u,int v)
{
static int pool_counter;
static Link pool[MAXM*4];
pool[pool_counter].to=v;
pool[pool_counter].next=link[u];
link[u]=&pool[pool_counter++];
}
void tarjan(int start)
{
static int DFN[MAXN];
static int LOW[MAXN];
static int stamp;
static int stack[MAXN];
static bool instack[MAXN];
static int top;
static bool visited[MAXN];
static int depth;
static Link* i[MAXN];
static int root[MAXN];
i[depth]=link[root[depth]=start];
DFN[root[depth]]=LOW[root[depth]]=++stamp;
instack[stack[top++]=root[depth]]=true;
visited[root[depth]]=true;
do
{
//printf(“root=%d LOW=%d DFN=%d\n”,root[depth]+1,LOW[root[depth]],DFN[root[depth]]);
if (i[depth])
{
if (!visited[i[depth]->to])
{
i[depth+1]=link[root[depth+1]=i[depth]->to];
DFN[root[depth+1]]=LOW[root[depth+1]]=++stamp;
instack[stack[top++]=root[depth+1]]=true;
visited[root[depth+1]]=true;
i[depth]=i[depth]->next;
depth++;
}
else if (instack[i[depth]->to])
{
LOW[root[depth]]=MIN(LOW[root[depth]],DFN[i[depth]->to]);
i[depth]=i[depth]->next;
}
else i[depth]=i[depth]->next;
}
else
{
if (LOW[root[depth]]==DFN[root[depth]])
{
//printf(“GET:”);
//do instack[stack[–top]]=false,printf(“%d “,stack[top]+1);
//while (stack[top]!=root[depth]);
//printf(“\n”);
do
{
instack[stack[–top]]=false;
if (isBar[stack[top]])
isBar[root[depth]]=true;
if (stack[top]!=root[depth])
money[root[depth]]+=money[stack[top]];
belong[stack[top]]=root[depth];
for (Link* j=link[stack[top]];j!=0;j=j->next)
insert(root[depth],j->to);
}
while (stack[top]!=root[depth]);
}
if (depth>0)
LOW[root[depth-1]]=MIN(LOW[root[depth-1]],LOW[root[depth]]);
depth–;
}
}
while (depth>=0);
}
/*BACKUP 1ST VERSION
void tarjan(int root)
{
static int DFN[MAXN];
static int LOW[MAXN];
static int stamp;
static int stack[MAXN];
static bool instack[MAXN];
static int top;
static bool visited[MAXN];
DFN[root]=LOW[root]=++stamp;
instack[stack[top++]=root]=true;
visited[root]=true;
for (Link* i=link[root];i!=0;i=i->next)
if (!visited[i->to])
{
tarjan(i->to);
LOW[root]=MIN(LOW[root],LOW[i->to]);
}
else if (instack[i->to])
LOW[root]=MIN(LOW[root],DFN[i->to]);
if (LOW[root]==DFN[root])
{
do
{
instack[stack[–top]]=false;
if (isBar[stack[top]])
isBar[root]=true;
if (stack[top]!=root)
money[root]+=money[stack[top]];
belong[stack[top]]=root;
for (Link* j=link[stack[top]];j!=0;j=j->next)
insert(root,j->to);
}
while (stack[top]!=root);
//printf(“GET:”);
//do instack[stack[–top]]=false,printf(“%d “,stack[top]+1);
//while (stack[top]!=root);
//printf(“\n”);
}
}
*/
int DP(int start)
{
static bool calced[MAXN];
static int MAX[MAXN];
start=belong[start];
if (!calced[start])
{
calced[start]=true;
for (Link* i=link[start];i!=0;i=i->next)
if (MAX[start]<DP(i->to))
MAX[start]=DP(i->to);
if (MAX[start]) MAX[start]+=money[start];
else if (isBar[start]) MAX[start]=money[start];
}
return MAX[start];
}