洛谷P3627:https://www.luogu.org/problemnew/show/P3627

思路

由于有强连通分量 所以我们可以想到先把整个图缩点

缩点完之后再建一次图 把点权改为边权 并把边权转为负数 即可用SPFA求最短路间接求最长路了

最后我们查询所有的酒吧 跳出最大的ans即可

思路简单 但是代码有些冗长

代码

#include<iostream>
#include<cstring>
using namespace std;
#define maxn 500010
int n,m,s,p,top,num,cnt,col,ans,t,w;
int h[maxn],de[maxn],st[maxn],dfn[maxn],low[maxn],co[maxn],money[maxn],sum[maxn],q[maxn],dis[maxn],x[maxn],y[maxn];
bool vis[maxn],exist[maxn];
struct Edge
{
int to;
int next;
int w;
}e[maxn];
void add(int u,int v)//Tarjan的边
{
e[++cnt].to=v;
e[cnt].next=h[u];
h[u]=cnt;
}
void read()//输入
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
cin>>x[i]>>y[i];
add(x[i],y[i]);
}
for(int i=;i<=n;i++)
cin>>money[i];
cin>>s;
}
void Add(int u,int v,int w)//SPFA的边
{
e[++cnt].w=w;
e[cnt].to=v;
e[cnt].next=h[u];
h[u]=cnt;
}
void Tarjan(int u)//标准Tarjan
{
dfn[u]=low[u]=++num;
vis[u]=;
st[++top]=u;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else
if(vis[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
col++;
while(st[top+]!=u)
{
sum[col]+=money[st[top]];//计算此强连通分量的总价值
co[st[top]]=col;
vis[st[top--]]=;
}
}
}
void SPFA()//标准SPFA
{
memset(dis,,sizeof(dis));
dis[co[s]]=-sum[co[s]];//负权
q[]=co[s];//把市中心所在的点入队
t=;
w=;
while(t<w)
{
t++;
int u=q[t];
exist[u]=;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!exist[v])
{
w++;
q[w]=v;
exist[v]=;
}
}
}
}
}
int main()
{
read();
for(int i=;i<=n;i++)
if(!dfn[i]) Tarjan(i);
cnt=;
memset(e,,sizeof(e));
memset(h,,sizeof(h));//注意清空边
for(int i=;i<=m;i++)
if(co[x[i]]!=co[y[i]])
Add(co[x[i]],co[y[i]],-sum[co[y[i]]]);//负权边
SPFA();
cin>>p;
for(int i=;i<=p;i++)//枚举所有酒吧求最大值
{
int bar;
cin>>bar;
if(-dis[co[bar]]>ans)
ans=-dis[co[bar]];
}
cout<<ans;
}

最新文章

  1. 【CoreAnimation】1 到 5
  2. InnoDB杂记
  3. springMVC和mybatis整合,jsp对时间进行格式化
  4. SpringMVC——自定义拦截器、异常处理以及父子容器配置
  5. APP消息推送:通知和透传
  6. (step4.2.5)hdu 1495(非常可乐——BFS)
  7. APUE学习笔记-一些准备
  8. OpenStack简单测试性能监控数据记录
  9. hdu_5719_Arrange(脑洞题)
  10. java 方法重载overload
  11. zend Framework的MVC模式的搭建
  12. 五 Struts 配置文件
  13. ORACLE not available
  14. Linux之环境搭建(一)
  15. 用JS更好的实现响应式布局
  16. WAMP中mysql服务突然无法启动 解决方法
  17. linux下mysql 5.7.22 安装
  18. 如何在MYSQL下所有指定数据库名下执行SQL
  19. php header utf8 插入header(&quot;Content-type: text/html; charset=utf-8&quot;);
  20. @SpringContext通过实现ApplicationContextAware接口动态获取bean

热门文章

  1. org.hibernate.QueryException: duplicate alias: r hibernate别名重复问题解决
  2. 02-使用注解配置spring
  3. 【Unity】工具类系列教程—— 代码自动化生成!
  4. File upload error - unable to create a temporary file
  5. Linux VFS机制简析(一)
  6. 【Postman】Postman的安装和使用
  7. winform代码生成器(二)
  8. vbScript: 编号成生不夠位數前面加零
  9. 详解WebApp与Native App的区别
  10. HTML字符实体名称/实体编号