【Luogu】P3627抢掠计划(缩点最短路)
2024-09-07 03:49:11
题目链接在此
有环当然一定尽量走环,这是搞缩点的人都知道的常识。
建了新图之后搞点权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 ;
}
最新文章
- 扫描内网活跃的ip
- 敏捷开发之Scrum扫盲篇
- ASP.NET MVC图片上传
- JAVA设计模式之解释器模式
- 一个Web页面的生命周期 ,面试常常被问到
- mobileconfig文件的签名和认证(signed、verified)
- Linux负载均衡软件LVS之二(安装篇)[转]
- [置顶] js综合应用:表格的四则运算
- Spring classPath:用法
- 从浏览器直接转跳到APP具体页面---(魔窗)MagicWindow使用教程
- How to Create Modifiers Using the API QP_MODIFIERS_PUB.PROCESS_MODIFIERS
- rubygem若干常用选项参数
- asp.net-缓存技术-20180409
- nginx 配置白名单
- 【ASP.NET 进阶】Flv视频文件在线播放示例
- JS方法 - 字符串处理函数封装汇总 (更新中...)
- 【Docker】性能测试监控平台搭建:InfluxDB+Grafana+Jmeter+cAdvisor
- Python导入模块-Import
- 切换java版本
- ci框架 用框架自带db 添加括号,比如 like 等等左右添加括号 解决办法
热门文章
- error: stray &#39;\343&#39; in program 问题解决
- AndroidStudio第一次提交项目代码到git服务器/github
- UIView和Masonry实现动画效果
- 【Web应用-Web作业】Web 作业无法直接运行 jar 文件
- MySQL性能优化奇技淫巧
- C语言二维数组作为函数参数
- javase(2)_递归&;迭代
- java在线聊天项目0.5版 解决客户端向服务器端发送信息时只能发送一次问题 OutputStreamWriter DataOutputStream socket.getOutputStream()
- OmniFocus
- ios之UIActivityIndicatorView