题目链接在此

有环当然一定尽量走环,这是搞缩点的人都知道的常识。

建了新图之后搞点权SPFA跑最长路。枚举每个酒吧选择最大值。

发现我的博客写的越来越水了

#include<cstdio>
#include<cctype>
#include<cstring>
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} inline long long max(long long a,long long b){ return a>b?a:b; }
inline long long min(long long a,long long b){ return a<b?a:b; } struct Edge{
int next,to;
}; struct Pic{
Edge edge[];
int head[],num;
inline void add(int from,int to){
edge[++num]=(Edge){head[from],to};
head[from]=num;
}
}Old,New; int que[];
int fsh[];
int f[],h,t=;
int stack[],top;
int dfn[],low[],ID;
int col[],cnt;
int val[];
bool vis[];
int dis[];
void tarjan(int x){
vis[x]=;
dfn[x]=low[x]=++ID;
stack[++top]=x;
for(int i=Old.head[x];i;i=Old.edge[i].next){
int to=Old.edge[i].to;
if(!dfn[to]){
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to]) low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x]){
vis[x]=;
col[x]=++cnt;
val[cnt]+=que[x];
while(stack[top]!=x){
vis[stack[top]]=;
val[cnt]+=que[stack[top]];
col[stack[top--]]=cnt;
}
top--;
}
}
int ans;
int main(){
int n=read(),m=read();
for(int i=;i<=m;++i){
int from=read(),to=read();
Old.add(from,to);
}
for(int i=;i<=n;++i) que[i]=read();
int s=read(),p=read();
for(int i=;i<=p;++i) fsh[i]=read();
for(int i=;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(int i=;i<=n;++i)
for(int j=Old.head[i];j;j=Old.edge[j].next){
int to=Old.edge[j].to;
if(col[i]!=col[to]) New.add(col[i],col[to]);
}
f[]=col[s];
memset(vis,,sizeof(vis));
dis[col[s]]=val[col[s]];
while(h<t){
h++;
int from=f[h];
vis[from]=;
for(int i=New.head[from];i;i=New.edge[i].next){
int to=New.edge[i].to;
if(dis[to]<dis[from]+val[to]){
dis[to]=dis[from]+val[to];
if(!vis[to]){
vis[to]=;
f[++t]=to;
}
}
}
}
for(int i=;i<=p;++i) ans=max(ans,dis[col[fsh[i]]]);
printf("%d",ans);
return ;
}

最新文章

  1. 扫描内网活跃的ip
  2. 敏捷开发之Scrum扫盲篇
  3. ASP.NET MVC图片上传
  4. JAVA设计模式之解释器模式
  5. 一个Web页面的生命周期 ,面试常常被问到
  6. mobileconfig文件的签名和认证(signed、verified)
  7. Linux负载均衡软件LVS之二(安装篇)[转]
  8. [置顶] js综合应用:表格的四则运算
  9. Spring classPath:用法
  10. 从浏览器直接转跳到APP具体页面---(魔窗)MagicWindow使用教程
  11. How to Create Modifiers Using the API QP_MODIFIERS_PUB.PROCESS_MODIFIERS
  12. rubygem若干常用选项参数
  13. asp.net-缓存技术-20180409
  14. nginx 配置白名单
  15. 【ASP.NET 进阶】Flv视频文件在线播放示例
  16. JS方法 - 字符串处理函数封装汇总 (更新中...)
  17. 【Docker】性能测试监控平台搭建:InfluxDB+Grafana+Jmeter+cAdvisor
  18. Python导入模块-Import
  19. 切换java版本
  20. ci框架 用框架自带db 添加括号,比如 like 等等左右添加括号 解决办法

热门文章

  1. error: stray &#39;\343&#39; in program 问题解决
  2. AndroidStudio第一次提交项目代码到git服务器/github
  3. UIView和Masonry实现动画效果
  4. 【Web应用-Web作业】Web 作业无法直接运行 jar 文件
  5. MySQL性能优化奇技淫巧
  6. C语言二维数组作为函数参数
  7. javase(2)_递归&amp;迭代
  8. java在线聊天项目0.5版 解决客户端向服务器端发送信息时只能发送一次问题 OutputStreamWriter DataOutputStream socket.getOutputStream()
  9. OmniFocus
  10. ios之UIActivityIndicatorView