The idea in front of this problem is the same as other solutions, which are all tarjan contractions. Then it is to ask for the maximum value of gold coins. I use memory search to express how much money can be stolen from the connection block numbered I with jiyi[i]. When I search, if I encounter a point that has been searched (I know how much money can be stolen from that point), I will directly return. Because each point of memory search will only be traversed once, the complexity of memory search should be O(n).
In addition, my code style is a little strange. Let's explain first: stk[tk] is the pointer of the stack and the stack (tarjan), num is the number of connecting blocks, tim timestamp, shuyu[i] is which connecting block point I belongs to, he [] is how much money there is in a connecting block, vis [] is whether a point is in the stack, jiuba [] is whether a point has a bar, suojb [] is the reduced connecting block. Is there a bar in. bian[],head[],ecnt are all the edges in the graph before the shrink point. If there is suffix x after the shrink point, it means the edge in the new graph after the shrink point.
#include<bits/stdc++.h> using namespace std; const int N=500005; int n,m,ecnt,s,p,tk,num,tim,ecntx,ans; int qian[N],head[N],dfn[N],low[N],stk[N],shuyu[N],he[N],headx[N],jiyi[N]; bool vis[N],jiuba[N],suojb[N]; struct aaa { int to,nxt; }bian[N],bianx[N]; inline int read()//Standard fast reading { int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} return f?-x:x; } inline void add(int a,int b)//Chain forward star edge; { bian[++ecnt].to=b; bian[ecnt].nxt=head[a]; head[a]=ecnt; } inline void addx(int a,int b)//After shrinking, the connecting block and the connecting block are edged. { bianx[++ecntx].to=b; bianx[ecntx].nxt=headx[a]; headx[a]=ecntx; } void tarjan(int u)//Standard tarjan { dfn[u]=low[u]=++tim; stk[++tk]=u;vis[u]=1; for(int i=head[u];i;i=bian[i].nxt) { int v=bian[i].to; if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if(vis[v])low[u]=min(low[u],low[v]); } if(dfn[u]==low[u]) { num++; while(stk[tk]!=u) { shuyu[stk[tk]]=num;//The connection block to which the record point belongs; vis[stk[tk]]=0; stk[tk]=0;tk--; } shuyu[stk[tk]]=num;//At this time, there is another point on the top of the stack in this connection block, and it will be executed again. vis[stk[tk]]=0; stk[tk]=0;tk--; } } void suo()//Shrinkage point; { for(int i=1;i<=n;i++) { he[shuyu[i]]+=qian[i];//Update the total amount of money in each Unicom block if(jiuba[i])suojb[shuyu[i]]=1;Update whether there is a bar in the Unicom block for(int j=head[i];j;j=bian[j].nxt) { int v=bian[j].to; if(shuyu[i]!=shuyu[v]) addx(shuyu[i],shuyu[v]);//If the starting point and the ending point are not in the same connecting block, the edge is added between the two connecting blocks; } } } int dfs(int dian)//If the new graph is a directed acyclic graph, then we can get dfs. { if(jiyi[dian])return jiyi[dian];//If the link block has been searched, that is, we know the maximum amount of money from this point, we will return directly; if(headx[dian]==0&&suojb[dian]==1)//If the connection block is 0 and there is a bar here, you can stop here and return the total amount of the connection block. { jiyi[dian]=he[dian]; return he[dian]; } if(headx[dian]==0&&suojb[dian]==0)return 0;//If the connection block is 0 but there is no bar, it can't stop here, so its contribution to the answer is 0; for(int i=headx[dian];i;i=bianx[i].nxt) { jiyi[dian]=max(jiyi[dian],dfs(bianx[i].to));//One of the multiple outputs of a connection block is the largest; } if(jiyi[dian]==0&&suojb[dian]==0)return 0; //Note: at this time, we think less about a situation. If there is no bar in a series of points on a path, then the robber can't stop on this path, but if there is no bar, the program will still follow this path; plus this sentence, if there is no bar at the back of the point and there is no bar here, then its contribution to the answer is 0, direct return 0; jiyi[dian]+=he[dian];//Add your own point weight to the memory array; return jiyi[dian];//Return the maximum amount of money from this point; } int main() { int a,b; n=read();m=read(); for(int i=1;i<=m;i++) { a=read();b=read(); add(a,b); //There's a strange error. You can't write add (read()); otherwise, it will go wrong. I don't know why. } for(int i=1;i<=n;i++) qian[i]=read(); s=read();p=read(); for(int i=1;i<=p;i++) jiuba[read()]=1; for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); suo(); ans=dfs(shuyu[s]); cout<<ans; return 0; }