BZOJ 1179 [Apio2009]Atm

题目大意

给你个有向图，请求出沿途点权值最大（经过两次获取一次权值）的一条路线使得其终点是标记点。

这道题就是Tarjan板子题，缩点之后跑一次最长路就可以了。

注意BFS是不可以的qwq

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,u,v,p[1000100],b[1000100],bars,S,ans,f[1000100],st[1000100],deep[1000100],low[1000100],re[1000100],tops,cnt;
int to[2000100],nex[2000100],head[1000100],nhead[1000100],tot;
bool use[1000100],ins[1000100];
void addedge(int tx,int ty)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;
}
void naddedge(int tx,int ty)
{
	to[++tot]=ty,nex[tot]=nhead[tx],nhead[tx]=tot;
}
void tarjan(int tx)
{
	st[++tops]=tx,use[tx]=true,ins[tx]=true;
	deep[tx]=low[tx]=++cnt;
	for(int i=head[tx];i;i=nex[i])
	{
		if(!use[to[i]]) tarjan(to[i]),low[tx]=min(low[tx],low[to[i]]);
		else if(ins[to[i]]) low[tx]=min(low[tx],deep[to[i]]);
	}
	if(deep[tx]==low[tx])
	{
		n++;
		re[n]=n;
		use[n]=true;
		int tmp;
		do
		{
			tmp=st[tops--],ins[tmp]=false;
			re[tmp]=n;
			p[n]+=p[tmp];
		}while(tmp!=tx);
	}
}
void topsort()
{
	for(int i=1;i<=n;++i)
		for(int j=head[i];j;j=nex[j])
			if(re[i]!=re[to[j]])
				naddedge(re[i],re[to[j]]);
	memset(use,false,sizeof use);
	priority_queue<pair<int,int> >q;
	q.push(make_pair(0,re[S]));
	f[re[S]]=p[re[S]];
	while(!q.empty())
	{
		int tmp=q.top().second;
		q.pop();
		//printf("%d\n",tmp);
		for(int i=nhead[tmp];i;i=nex[i])
			if(f[to[i]]<f[tmp]+p[to[i]])
			{
				f[to[i]]=f[tmp]+p[to[i]];
				q.push(make_pair(f[to[i]],to[i]));
			}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--) scanf("%d%d",&u,&v),addedge(u,v);
	for(int i=1;i<=n;++i) scanf("%d",p+i);
	scanf("%d%d",&S,&bars);
	for(int i=1;i<=bars;++i) scanf("%d",b+i);
	for(int i=1;i<=n;++i) if(!use[i]) tarjan(i);
	topsort();
	for(int i=1;i<=bars;++i)
		ans=max(ans,f[re[b[i]]]);
	printf("%d\n",ans);
}