题目传送门：https://loj.ac/problem/10096
-------------------------------------------------------------------------------------------------------
强联通分量内的ATM只要有一个可以抢到就都可以抢到的，所以要缩点。
当然，要统计整个分量内可以抢到的钱的和。
分量内只要有一个路口有酒吧，那么这个分量就可以作为结束点进行庆祝，所以要统计每个分量内是否有酒吧。
然后在缩点后的有向无环图上进行拓扑排序，然后进行DP，求出到每个分量可以抢到的最大钱数。
最后把所有抢到钱的分量中，求出有酒吧且最大的就是答案。
-------------------------------------------------------------------------------------------------------
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5e5+10; 4 const int maxm=5e5+10; 5 int n,m; 6 struct edge 7 { 8 int u,v,nxt; 9 }e[maxm],ee[maxm]; 10 int head[maxn],js,headd[maxn],jss; 11 void addage(edge e[],int head[],int &js,int u,int v) 12 { 13 e[++js].u=u;e[js].v=v; 14 e[js].nxt=head[u];head[u]=js; 15 } 16 int dfn[maxn],low[maxn],st[maxn],top,cnt,lt[maxn],lts; 17 void tarjan(int u) 18 { 19 dfn[u]=low[u]=++cnt; 20 st[++top]=u; 21 for(int i=head[u];i;i=e[i].nxt) 22 { 23 int v=e[i].v; 24 if(!dfn[v]) 25 { 26 tarjan(v); 27 low[u]=min(low[u],low[v]); 28 } 29 else if(!lt[v]) 30 low[u]=min(low[u],dfn[v]); 31 } 32 if(dfn[u]==low[u]) 33 { 34 lt[u]=++lts; 35 while(st[top]!=u)lt[st[top--]]=lts; 36 --top; 37 } 38 } 39 int money[maxn],moneys[maxn],s,p; 40 bool isp[maxn],isps[maxn]; 41 int f[maxn]; 42 bool inq[maxn]; 43 queue<int>q; 44 void dfs(int x) 45 { 46 q.push(x); 47 while(!q.empty()) 48 { 49 int u=q.front();q.pop();inq[u]=0; 50 for(int i=headd[u];i;i=ee[i].nxt) 51 { 52 int v=ee[i].v; 53 if(f[u]+moneys[v]>f[v]) 54 { 55 f[v]=f[u]+moneys[v]; 56 if(!inq[v]) 57 { 58 q.push(v); 59 inq[v]=1; 60 } 61 } 62 } 63 } 64 } 65 int main() 66 { 67 scanf("%d%d",&n,&m); 68 for(int u,v,i=0;i<m;++i) 69 { 70 scanf("%d%d",&u,&v); 71 addage(e,head,js,u,v); 72 } 73 for(int i=1;i<=n;++i)scanf("%d",money+i); 74 scanf("%d%d",&s,&p); 75 for(int x,i=0;i<p;++i) 76 { 77 scanf("%d",&x); 78 isp[x]=1; 79 } 80 for(int i=1;i<=n;++i) 81 if(!dfn[i])tarjan(i); 82 for(int i=1;i<=n;++i) 83 { 84 moneys[lt[i]]+=money[i]; 85 if(isp[i])isps[lt[i]]=1; 86 } 87 for(int u=1;u<=n;++u) 88 for(int i=head[u];i;i=e[i].nxt) 89 { 90 int v=e[i].v; 91 if(lt[u]!=lt[v])addage(ee,headd,jss,lt[u],lt[v]); 92 } 93 f[lt[s]]=moneys[lt[s]]; 94 dfs(lt[s]); 95 int ans=0; 96 for(int i=1;i<=lts;++i)if(isps[i])ans=max(ans,f[i]); 97 cout<<ans; 98 return 0; 99 }