【强连通缩点+最长路】抢掠计划

抢掠计划

Siruseri城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，

在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri

的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri有史以来最惊天动地的 ATM 抢劫。他将从市中心

出发，沿着单向道路行驶，抢劫所有他途径的ATM 机，最终他将在一个酒吧庆

祝他的胜利。

使用高超的黑客技术，他获知了每个ATM 机中可以掠取的现金数额。他希

望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可

以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机

里面就不会再有钱了。

例如，假设该城中有6个路口，道路的连接情况如下图所示： 

市中心在路口 1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表

示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢

劫的现金总数为47，实施的抢劫路线是：1-2-4-1-2-3-5。

输入格式

第一行包含两个整数 N、M。N 表示路口的个数，M表示道路条数。接下来

M行，每行两个整数，这两个整数都在 1到 N 之间，第i+1 行的两个整数表示第

i 条道路的起点和终点的路口编号。接下来 N 行，每行一个整数，按顺序表示每

个路口处的ATM机中的钱数。接下来一行包含两个整数 S、P，S表示市中心的

编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有 P个整数，表示

P个有酒吧的路口的编号。

输出格式

输出一个整数，表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多

的现金总数。

数据范围

50%的输入保证 N,  M<=3000。所有的输入保证 N,  M<=500000。每个 ATM

机中可取的钱数为一个非负整数且不超过 4000。输入数据保证你可以从市中心

沿着Siruseri的单向的道路到达其中的至少一个酒吧。

输入样例

6 7

1 2

2 3

3 5

2 4

4 1

2 6

6 5

10

12

8

16

1

5

1 4

4 3 5 6

输出样例

47

和上一道题如出一辙，此题是一个简化版本，不用再赘述。

只是因为ans = MAX(ans,dist[Belong[bar[i]]]+size[Belong[S]]);  

打成了ans = MAX(ans,dist[bar[i]]+size[Belong[S]]);    而悲剧地爆零了

#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include <cstdio>
#include <map>

const long maxn = 500010;
const long MOD = 500010;
typedef long long ll;
long n;long m;
long S;long P;
long money[maxn];
long bar[maxn];
long DFN[maxn];
long LOW[maxn];
bool InStack[maxn];
long Stack[maxn];
long top  = 0;
long TIME = 0;
long Bcnt = 0;
long Belong[maxn];
long size[maxn];
long que[MOD];
bool vis[maxn];
long dist[maxn];
std::map<ll,bool> connected;
#define POS(a,b) (((ll)a-1)*(ll)m+(ll)b-1ll)
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)

struct node
{
	long index;
	node* next;	
};
node* head[maxn];
node* head2[maxn];

void insert(long a,long b)
{
	node* tmp = new node;
	tmp->index = b;
	tmp->next = head[a];
	head[a] = tmp;
}

void init()
{
	scanf("%ld%ld",&n,&m);
	for (long i=1;i<m+1;i++)
	{
		long a;long b;
		scanf("%ld%ld",&a,&b);
		insert(a,b);
	}
	for (long i=1;i<n+1;i++)
	{
		scanf("%ld",money+i);
	}
	scanf("%ld%ld",&S,&P);
	for (long i=1;i<P+1;i++)
	{
		scanf("%ld",bar+i);
	}
}

void tarjan(long u)
{
	DFN[u] = LOW[u] = ++TIME;
	InStack[u] = true;
	Stack[++top] = u;
	for (node* next=head[u];next;next=next->next)
	{
		long v = next->index;
		if (!DFN[v])
		{
			tarjan(v);
			LOW[u] = MIN(LOW[u],LOW[v]);
		}
		else if(InStack[v])
		{
			LOW[u] = MIN(LOW[u],DFN[v]);
		}
	}
	if (DFN[u] == LOW[u])
	{
		++Bcnt;
		long v;
		do
		{
			v = Stack[top--];
			InStack[v]= false;
			Belong[v] = Bcnt;
			size[Bcnt]+=money[v]; 
		}while(v != u);
	}
}

void SPFA()
{
	long l = 0;
	long r = 0;
	que[++r] = Belong[S];
	while (l != r)
	{
		l = (l+1) % MOD;
		long u = que[l];
		vis[u] = false;
		for (node* vv=head2[u];vv;vv=vv->next)
		{
			long v = vv->index;
			if (dist[v]<dist[u]+size[v])
			{
				dist[v]=dist[u]+size[v];
				if (!vis[v])
				{
					vis[v] = true;
					r = (r+1) % MOD;
					que[r] = v;
				}
			}
		}
	}	
}

void insert2(long a,long b)
{
	node* tmp = new node;
	tmp->index = b;
	tmp->next = head2[a];
	head2[a] = tmp;
}

void rebuild()
{
	for (long u=1;u<n+1;u++)
	{
		for (node* vv=head[u];vv;vv=vv->next)
		{
			long v = vv->index;
			long B1 = Belong[u];
			long B2 = Belong[v];
			if (B1 != B2 && !connected[POS(B1,B2)])
			{
				connected[POS(B1,B2)] = true;
				insert2(B1,B2);
			}
		}
	}
}

int main()
{
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout); 
	init();
	for (long i=1;i<n+1;i++)
		if (!DFN[i]) tarjan(i);
	rebuild();
	SPFA();
	long ans = 0;
	for (long i=1;i<P+1;i++)
	{
		ans = MAX(ans,dist[Belong[bar[i]]]+size[Belong[S]]);	
	}
	printf("%ld",ans);
	return 0;
}