【強連通縮點+最長路】搶掠計劃

搶掠計劃

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;
}