咕了四个小时整整一晚上
P3627 [APIO2009]
抢掠计划(https://www.luogu.org/problemnew/show/P3627)
不难看出答案即为该有向图的最长链长度（允许重复
我会dp！
但是图中可能有环，不满足dp的无后效性假设
我会tarjan！
（您太强了）
在同一个强连通分量里的点一定可以互相到达，tarjan缩点之后，将每一个强联通分量看作一个点，价值就是其中所有银行的价值总和
缩点完成之后我们重新构造一个新的图，原来连接两个点的边改成连向两个点所在的强连通分量（如果在同一个强连通分量里？这就是环了不用管）
接着本来想写bfs求最长路……写着写着感觉就变成spfa了（笑哭）
最后我们算出起点到每一个强连通分量的最长路，枚举每一个点，判断有酒吧就更新答案
#include<bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
using namespace std;
int n,m;
#define maxn 500009
vector<int> son[maxn];
int c[maxn];
bool bar[maxn];
void add(int x,int y)
{
son[x].push_back(y);
}
int s,p;
int dfsn[maxn],lowlink[maxn];
int sta[maxn];
int top=;
int dfs_clock=;
int scc_cnt=;//有多少个强连通分量
int scc[maxn];//每个点在那个强连通分量里
int val[maxn];//每个点所在的强连通分量的价值总和
int q[maxn];
int vy[maxn];//每个强连通分量的价值总和
void dfs_scc(int x)//tarjan!!!
{
dfsn[x]=lowlink[x]=++dfs_clock;
sta[++top]=x;
for(int i=;i<son[x].size();i++)
{
int now=son[x][i];
if(!dfsn[now])
{
dfs_scc(now);
lowlink[x]=min(lowlink[x],lowlink[now]);
}else if(!scc[now])
{
lowlink[x]=min(lowlink[x],dfsn[now]);
}
}
if(lowlink[x]==dfsn[x])
{
scc_cnt++;
int ans=;
int p=;
while(sta[top]!=x)
{
q[++p]=sta[top];//挖坑提示：q是一个用来记录的数组，把强连通分量中的点记录下来，这个q一定要开全局变量，不用memset
//如果每次在递归中定义一个q，一轮就会爆栈！！！！本地出现蜜汁错误，洛谷ide却没问题！！
ans+=c[sta[top]];
scc[sta[top--]]=scc_cnt;
}
top--;
scc[x]=scc_cnt;
q[++p]=x;
ans+=c[x];
vy[scc_cnt]=ans;
for(int i=;i<=p;i++)
{
val[q[i]]=ans;
}
}
}
struct node{
int x,y;
}e[maxn];;
vector<int> newmap[maxn];
int in[maxn],d[maxn];
struct point{
int x,step;
};
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
e[i].x=x,e[i].y=y;
}
for(int i=;i<=n;i++)
{
scanf("%d",&c[i]);
}
scanf("%d%d",&s,&p);
memset(bar,,sizeof(bar));
for(int i=;i<=p;i++)
{
int x;
scanf("%d",&x);
bar[x]=;
}
for(int i=;i<=n;i++)
{
if(!dfsn[i])dfs_scc(i);
}
for(int i=;i<=m;i++)//一条边的两个端点必须不在同一个强连通分量里
{
if(scc[e[i].x]!=scc[e[i].y])
{
newmap[scc[e[i].x]].push_back(scc[e[i].y]);
}
} queue<int> q;
q.push(scc[s]);
d[scc[s]]=val[s];
while(!q.empty())//广搜，不，事实上这是一个spfa
{
int xx=q.front();
int x=xx;
q.pop();
// printf("x:%d %d\n",x,xx.step);
for(int i=;i<newmap[x].size();i++)
{
int to=newmap[x][i];
if(d[to]>=d[x]+vy[to])continue; //类似于松弛的操作……
d[to]=max(d[to],d[x]+vy[to]);
q.push(to);
}
}
int ans=;
for(int i=;i<=n;i++)
{
if(bar[i])//如果这个点有酒吧，那么我们就统计一下它所在的强连通分量的答案
{
ans=max(ans,d[scc[i]]);
}
}
printf("%d\n",ans);
return ;
}