• 给定一张有向图,每个点有钱,走过一遍钱就被抢走了,每个点和边都可以走多次,给定一些目的地,问一通乱抢之后到任意一个目的地能拿到的最多钱数。
#include<cstring>//裸的 tajian+spfa
#include<ctype.h>
#include<cstdio>
#include<queue>
#define N 1000005
using namespace std;
bool in[N],pp[N],vis[N],v[N];
int bel[N],VAL[N],size[N],hea[N],val[N],sta[N],low[N],dnf[N],hea2[N],dis[N];
int tot,ans,top,pt,dfs_clock,s,p,x,y,n,m;
struct NODE{
int nex,to;
}nex[N];
NODE nex2[N];
inline void add(int x,int y){
nex[++tot].nex=hea[x];
nex[tot].to=y;
hea[x]=tot;
}
int input(){
char c='^';
int sum=0;
c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
return sum;
}
void tajian(int curr){
vis[sta[++top]=curr]=1;
dnf[curr]=low[curr]=++dfs_clock;
for(int i=hea[curr];i;i=nex[i].nex){
if(!dnf[nex[i].to]){
tajian(nex[i].to);
low[curr]=min(low[curr],low[nex[i].to]);
}
else if(vis[nex[i].to]){
low[curr]=min(low[curr],dnf[nex[i].to]);
}
}
if(low[curr]==dnf[curr]){
vis[curr]=0;
VAL[bel[curr]=++tot]+=val[curr];
while(sta[top]!=curr){
VAL[bel[sta[top]]=tot]+=val[sta[top]];
vis[sta[top--]]=0;
}
top--;
}
}
inline void rbuild(){//重新建边
for(int i=1;i<=n;i++)
for(int j=hea[i];j;j=nex[j].nex){
int dmf=nex[j].to;
if(bel[i]!=bel[dmf]){
nex2[++tot].to=bel[dmf];
nex2[tot].nex=hea2[bel[i]];
hea2[bel[i]]=tot;
}
}
}
inline void spfa(int s){
queue <int>q ;
dis[s]=VAL[s];
v[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=hea2[x];i;i=nex2[i].nex){
if(dis[x]+VAL[nex2[i].to]>dis[nex2[i].to]){
dis[nex2[i].to]=dis[x]+VAL[nex2[i].to];
if(!v[nex2[i].to]){
v[nex2[i].to]=1;
q.push(nex2[i].to);
}
}
}
v[x]=0;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
x=input();y=input();
add(x,y);
}
for(int i=1;i<=n;i++)
val[i]=input();
s=input();p=input();
for(int i=1;i<=n;i++)
if(!bel[i]) tajian(i);
tot=0;
rbuild();
spfa(bel[s]);
ans=0;
for(int i=1;i<=p;i++){
x=input();
ans=max(ans,dis[bel[x]]);
}
printf("%d",ans);
return 0;
}