hszxoj ATM
-
题目描述：$Siruseri$ 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 $Siruseri$ 银行的 $ATM$ 取款机。令人奇怪的是，$Siruseri$ 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。$Bandit ji$ 计划实施 $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$ 个有酒吧的路口的编号 $N, M<=500000$ 。每个 $ATM$ 机中可取的钱数为一个非负整数且不超过 $4000$ 。 输入数据保证你可以从市中心沿着 $Siruseri$ 的单向的道路到达其中的至少一个酒吧。
-
输出格式：输出一个整数，表示 $Banditji$ 从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
-
可以想到 $spfa$ 跑最长路 $\Large{but}$ $\Large{N,M<=500000}$
-
这就比较该死，直接 $spfa$ 一定会超时，所以就用到 $\large{tarjan缩点}$
-
缩完点后，再跑 $spfa$ 就可以了
-
代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=500001;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool f=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(f?x:~x+1);
}
vector<int>e[N];
stack<int>sta;
queue<int> q;
int n,m,s,p,bar,ans,sccnt,tot;
int from[N],to[N],w[N],dfn[N],low[N],color[N],siz[N],d[N];
bool v[N],ins[N];
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
sta.push(x),ins[x]=1;
for(int y:e[x])
{
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(ins[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
int y;++sccnt;
while(y!=x)
y=sta.top(),
sta.pop(),
ins[y]=0,
color[y]=sccnt,
siz[sccnt]+=w[y];
}
}
void spfa(int s)
{
q.push(s);
d[s]=siz[s];
v[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
v[x]=0;
for(int y:e[x])
{
if(d[y]<d[x]+siz[y])
{
d[y]=d[x]+siz[y];
if(!v[y]) q.push(y),v[y]=1;
}
}
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(m);
for(int i=1;i<=m;i++)
read(from[i]),read(to[i]),
e[from[i]].push_back(to[i]);
for(int i=1;i<=n;i++) read(w[i]);
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
memset(e,0,sizeof(e));
for(int i=1;i<=m;i++)
if(color[from[i]]!=color[to[i]])
e[color[from[i]]].push_back(color[to[i]]);
read(s),read(p);
spfa(color[s]);
for(int i=1;i<=p;i++) read(bar),ans=max(ans,d[color[bar]]);
cout<<ans;
}