题目传送门: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 }

最新文章

  1. 安装配置dradis
  2. 高性能javascript学习笔记系列(3) -DOM编程
  3. .NET之委托
  4. 他们在军训,我在搞OI(三)
  5. 一,XAML基础
  6. visuall assist x 破解方法
  7. css实现缩进无限嵌套
  8. Uncaught TypeError: Object [object Object] has no method &#39;live&#39;
  9. Android 弹出通知Toast的使用
  10. 用python做一个搜索引擎(Pylucene)
  11. python dlib opencv 人脸68点特征检测
  12. 文件搜索神器之everything
  13. EZ 2018 06 02 NOIP2018 模拟赛(十七)
  14. 20165321实验一Java开发环境的熟悉-1
  15. 力扣(LeetCode) 1010. 总持续时间可被 60 整除的歌曲
  16. 解决tomcat下面部署多个项目log4j的日志输出会集中输出到一个项目中的问题
  17. golang显示本机IP代码
  18. 使用Xshell和Xftfp部署简单的项目
  19. 项目记录 -- config2html 理解
  20. Geolocation 地理定位

热门文章

  1. JAVA 实体类List&lt;Entity &gt;转 List&lt;Map&gt;
  2. 多维数组遍历.php
  3. C/C++ 弱符号
  4. 远程分支删除后,git branch -a还能看到的解决方法
  5. 电脑加载有文件的CD、DVD驱动器图标修改
  6. MongoDB 基础手册(一)
  7. Java高并发与多线程(一)-----概念
  8. 2021年了,`IEnumerator`、`IEnumerable`还傻傻分不清楚?
  9. 2021新年 Vue3.0 + Element UI 尝鲜小记
  10. Go中由WaitGroup引发对内存对齐思考