Tarjan缩点+Spfa最长路【p3627】[APIO2009] 抢掠计划

\(Tarjan\)缩点跑最长路,

在求强联通分量的时候维护每个联通分量的\(val\)(即当前强联通分量中所有\(atm\)的钱数.

不能再次建边的时候再求.(会出锅,但是原理我不太知道。

再对强联通分量建边跑最长路即可.

注意：\(Dijkstra\)的贪心策略不可跑最长路。

这里数组可以重复使用,不过这题没有卡数组,就没有重复使用了 qwq.

代码

#include<cstdio>

#include<cctype>

#include<queue>

#define N 500008

#define R register

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m,head[N],tot,low[N],dfn[N],col,belong[N],idx,stk[N],pos;

int val[N],v[N],h[N],ttt,p,t[N],dis[N],top,s,ans;

struct cod{int u,v;}edge[N<<2],e[N<<2];

bool inq[N],vis[N];

inline void add(int x,int y)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	head[x]=tot;

}

inline void ado(int x,int y)

{

	e[++ttt].u=h[x];

	e[ttt].v=y;

	h[x]=ttt;

}

inline void spfa(int s)

{

	for(R int i=1;i<=col;i++)dis[i]=-214748364;

	queue<int>q;

	q.push(s);vis[s]=true;dis[s]=val[s];

	while(!q.empty())

	{

		int u=q.front();q.pop();vis[u]=false;

		for(R int i=h[u];i;i=e[i].u)

		{

			if(dis[e[i].v]<dis[u]+val[e[i].v])

			{

				dis[e[i].v]=dis[u]+val[e[i].v];

				if(!vis[e[i].v])

				{

					vis[e[i].v]=true;

					q.push(e[i].v);

				}

			}

		}

	}

	for(R int i=1;i<=p;i++)

		ans=max(ans,dis[belong[t[i]]]);

	printf("%d",ans);

}

void tarjan(int x)

{

	dfn[x]=low[x]=++idx;

	stk[++top]=x;inq[x]=true;

	for(R int i=head[x];i;i=edge[i].u)

	{

		if(!dfn[edge[i].v])

		{

			tarjan(edge[i].v);

			low[x]=min(low[x],low[edge[i].v]);

		}

		else if(inq[edge[i].v])

			low[x]=min(low[x],dfn[edge[i].v]);

	}

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

	{

		col++;

		int now=-1;

		while(now!=x)

		{

			now=stk[top--];

			inq[now]=false;

			belong[now]=col;

			val[col]+=v[now];

		}

	}

}

int main()

{

	in(n),in(m);

	for(R int i=1,x,y;i<=m;i++)

	{

		in(x),in(y);

		add(x,y);

	}

	for(R int i=1;i<=n;i++)in(v[i]);

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

		if(!dfn[i])tarjan(i);

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

		for(R int j=head[i];j;j=edge[j].u)

			if(belong[edge[j].v]!=belong[i])

				ado(belong[i],belong[edge[j].v]);

	in(s);in(p);

	for(R int i=1;i<=p;i++)in(t[i]);

	spfa(belong[s]);

}