【解题报告】洛谷P3627 抢掠计划
题目链接
https://www.luogu.com.cn/problem/P3627
思路
简要题意:
一个有向有环图,每个点有一个权值,请问,从某一个点出发,到某些特殊的点作为终点,经过点的时候可以得到它的权值,并且该点权值变为0,每个点可以走任意多次,请问可以得到的最大权值是多少
首先,这道题目中说了是有向有环图,我们再结合酒吧的定义,和路径可以走任何多遍,知道了,我们可以把一个强连通分量里面的点全部缩成一个,权值为所有里面的点的和,如果里面有酒吧的话,就把这个缩的点变成酒吧,以此类推
这里我们用强连通分量缩点需要使用到tarjan算法,然后跑一个最长路就可以了
但是这里还有一点需要注意的就是,如何把点权转化为边权(纯属因为边权更加好算
然后我们就可以快乐地玩耍了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int maxn=500005;
struct edge{
int e,val,next;
}ed[maxn<<1];
int m,n,p,s,en;
int belong[maxn];
int u[maxn],v[maxn],w[maxn];
int first[maxn],bar[maxn],dis[maxn];
int dfn[maxn],low[maxn],stk[maxn],sum[maxn];
bool vis[maxn];
queue <int> q;
int ans=0,size=0,tot=0,total=0;
void add(int u,int v)
{
en++;
ed[en].e=v;
ed[en].next=first[u];
first[u]=en;
}
void add2(int u,int v,int w)
{
en++;
ed[en].e=v;
ed[en].val=w;
ed[en].next=first[u];
first[u]=en;
}
void tarjan(int x)
{
dfn[x]=low[x]=++total;
stk[++size]=x;
vis[x]=true;
for(int i=first[x];i;i=ed[i].next)
{
int e=ed[i].e;
if(!dfn[e])
{
tarjan(e);
low[x]=min(low[x],low[e]);
}
else if(vis[e])
low[x]=min(low[x],dfn[e]);
}
if(dfn[x]==low[x])
{
tot++;
do{
int tp=stk[size];
sum[tot]+=w[tp];
vis[tp]=false;
belong[tp]=tot;
}while(stk[size--]!=x);
}
}
void spfa(int s)
{
for(int i=1;i<=tot;i++) dis[i]=0;
int gs=belong[s];
q.push(gs);
vis[gs]=true;
dis[gs]=sum[gs];
while(!q.empty())
{
int h=q.front();q.pop();
vis[h]=false;
for(int i=first[h];i;i=ed[i].next)
{
int e=ed[i].e;
if(dis[e]<dis[h]+ed[i].val)
{
dis[e]=dis[h]+ed[i].val;
if(!vis[e])
{
q.push(e);
vis[e]=true;
}
}
}
}
}
int main()
{
en=0;
memset(ed,0,sizeof(ed));
memset(first,0,sizeof(first));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i];
add(u[i],v[i]);
}
for(int i=1;i<=n;i++)
cin>>w[i];
cin>>s>>p;
for(int i=1;i<=p;i++)
cin>>bar[i];
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
en=0;
memset(ed,0,sizeof(ed));
memset(first,0,sizeof(first));
for(int i=1;i<=m;i++)
if(belong[u[i]]!=belong[v[i]])
add2(belong[u[i]],belong[v[i]],sum[belong[v[i]]]);
spfa(s);
for(int i=1;i<=p;i++)
ans=max(ans,dis[belong[bar[i]]]);
cout<<ans<<'\n';
return 0;
}