【jzoj 4771】【登山】【人工スタック】【図論】【強連通量】
タイトルの大意
図に向かって各点に価値があり、出発点から与えられた点に集中する一つの点に行くと停止できます.最大の価値を求めて、繰り返しても価値がありません.
問題を解く構想
tarjanの後に位相の順序dpによってすぐできて、穴のは点が多くて人工の倉庫を打つかもしれません.
コード
図に向かって各点に価値があり、出発点から与えられた点に集中する一つの点に行くと停止できます.最大の価値を求めて、繰り返しても価値がありません.
問題を解く構想
tarjanの後に位相の順序dpによってすぐできて、穴のは点が多くて人工の倉庫を打つかもしれません.
コード
#include<set>
#include
#include
#include
#include
#define LF double
#define LL long long
#define max(n1,n2) ((n1>n2)?n1:n2)
#define min(n1,n2) ((n1>n2)?n2:n1)
#define fo(i,j,k) for(LL i=j;i<=k;i++)
#define fd(i,j,k) for(LL i=j;i>=k;i--)
using namespace std;
int const maxn=500000,maxm=500000,inf=2147483647;
LL n,m,gra,top,top2,time,s,p,u[maxm+10],v[maxm+10],val[maxm+10],to[maxm+10],
next[maxm+10],begin[maxn+10],dfn[maxn+10],low[maxn+10],st[maxn+10],st2[maxn+10],
inst[maxn+10],bel[maxn+10],save[maxn+10],f[maxn+10],pre[maxn+10];
void insert(LL u,LL v){
to[++gra]=v;
next[gra]=begin[u];
begin[u]=gra;
}
void tarjan(LL be){
inst[st[++top]=be]=1;
st2[++top2]=be;
LL now;
for(;top2;){
now=st2[top2];
if(save[st2[top2]]){
int bb;
bb++;
}
if(!dfn[now])dfn[now]=low[now]=++time;
for(;begin[now];begin[now]=next[begin[now]])
if(!dfn[to[begin[now]]]){
inst[st[++top]=st2[++top2]=to[begin[now]]]=1;
break;
}else if(inst[to[begin[now]]])low[now]=min(low[now],dfn[to[begin[now]]]);
if(!begin[now]){
if(dfn[now]==low[now]){
for(;st[top]!=now;bel[st[top]]=now,val[now]+=val[st[top]],save[now]|=save[st[top]],inst[st[top--]]=0);
bel[st[top]]=now;inst[st[top--]]=0;
}
low[st2[top2-1]]=min(low[st2[top2-1]],low[st2[top2]]);
st2[top2--];
}
}
}
int main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
scanf("%lld%lld",&n,&m);
fo(i,1,m){
scanf("%lld%lld",&u[i],&v[i]);
insert(u[i],v[i]);
}
fo(i,1,n)scanf("%d",&val[i]);
scanf("%lld%lld",&s,&p);
fo(i,1,p){
LL x;scanf("%lld",&x);
save[x]=1;
}
tarjan(s);
gra=0;memset(begin,0,sizeof(begin));
fo(i,1,m)
if(bel[u[i]]&&bel[v[i]]&&bel[u[i]]!=bel[v[i]])insert(bel[u[i]],bel[v[i]]),pre[v[i]]++;
LL l=0,r=0,now;
st[++r]=s;
for(;l!=r;){
now=st[++l];
for(LL i=begin[now];i;i=next[i]){
pre[to[i]]--;
if(!pre[to[i]])inst[st[++r]=to[i]]=1;
}
}
fd(i,r,1){
now=st[i];
for(LL i=begin[now];i;i=next[i])
f[now]=max(f[now],f[to[i]]);
if(save[now]||f[now])f[now]+=val[now];
}
printf("%lld",f[s]);
return 0;
}