【bzoj1179】[Apio2009]Atm Tarjan缩点+Spfa最长路

题目描述

输入

第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号

输出

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

样例输入

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

样例输出

题解

Tarjan缩点+Spfa最长路

首先每个强连通分量中的所有点都可以相互经过且只能获得一次点权，所以需要先用Tarjan缩点再跑最长路。

这里懒了直接跑了Spfa，其实拓扑排序+dp应该更快

#include <cstdio>

#include <queue>

#define N 500010

using namespace std;

queue<int> q;

struct data

{

	int head[N] , to[N] , next[N] , cnt , v[N];

	void add(int x , int y)

	{

		to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;

	}

}A , B;

int deep[N] , low[N] , tot , sta[N] , ins[N] , vis[N] , top , bl[N] , num , f[N] , dis[N] , inq[N];

void tarjan(int x)

{

	int i;

	deep[x] = low[x] = ++tot , sta[++top] = x , vis[x] = ins[x] = 1;

	for(i = A.head[x] ; i ; i = A.next[i])

	{

		if(!vis[A.to[i]]) tarjan(A.to[i]) , low[x] = min(low[x] , low[A.to[i]]);

		else if(ins[A.to[i]]) low[x] = min(low[x] , deep[A.to[i]]);

	}

	if(deep[x] == low[x])

	{

		int t;

		num ++ ;

		do

		{

			t = sta[top -- ];

			bl[t] = num , ins[t] = 0;

			B.v[bl[t]] += A.v[t];

		}while(t != x);

	}

}

void spfa(int s)

{

	int x , i;

	dis[s] = B.v[s] , q.push(s);

	while(!q.empty())

	{

		x = q.front() , q.pop() , inq[x] = 0;

		for(i = B.head[x] ; i ; i = B.next[i])

		{

			if(dis[B.to[i]] < dis[x] + B.v[B.to[i]])

			{

				dis[B.to[i]] = dis[x] + B.v[B.to[i]];

				if(!inq[B.to[i]]) inq[B.to[i]] = 1 , q.push(B.to[i]);

			}

		}

	}

}

int main()

{

	int n , m , i , j , x , y , ans = 0;

	scanf("%d%d" , &n , &m);

	while(m -- ) scanf("%d%d" , &x , &y) , A.add(x , y);

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &A.v[i]);

	for(i = 1 ; i <= n ; i ++ ) if(!vis[i]) tarjan(i);

	for(i = 1 ; i <= n ; i ++ )

		for(j = A.head[i] ; j ; j = A.next[j])

			if(bl[i] != bl[A.to[j]])

				B.add(bl[i] , bl[A.to[j]]);

	scanf("%d%d" , &x , &y) , spfa(bl[x]);

	while(y -- ) scanf("%d" , &x) , ans = max(ans , dis[bl[x]]);

	printf("%d\n" , ans);

	return 0;

}

巴特西

【bzoj1179】[Apio2009]Atm Tarjan缩点+Spfa最长路

最新文章

热门文章