咕了四个小时整整一晚上

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 ;
}
05-11 18:20