题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1179

tarjan 缩环,然后求到有酒吧的点的最长路即可;

但一开始想缩环后用拓扑序求答案,不由分说的秒WA了,不知道为什么...

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
int const maxn=5e5+;
int n,m,hd[maxn],ct,deg[maxn],col[maxn],cr,head[maxn],sta[maxn],top;
int st,xt,dfn[maxn],low[maxn],tim,a[maxn],p;
ll val[maxn],ans,dis[maxn];
bool vis[maxn],bar[maxn],b[maxn];
queue<int>q;
struct N{
int to,nxt;
N(int t=,int n=):to(t),nxt(n) {}
}ed[maxn],edge[maxn];
void tarjan(int x)
{
dfn[x]=low[x]=++tim;
vis[x]=; sta[++top]=x;
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if(!dfn[u=ed[i].to])tarjan(u),low[x]=min(low[x],low[u]);
else if(vis[u])low[x]=min(low[x],dfn[u]);
}
if(low[x]==dfn[x])
{
int y; cr++;
while((y=sta[top])!=x)
{
vis[y]=; col[y]=cr; top--;
val[cr]+=a[y];
if(bar[y])b[cr]=;
}
vis[x]=; col[x]=cr; top--;
val[cr]+=a[x]; if(bar[x])b[cr]=;
}
}
//void topo()
//{
// memset(vis,0,sizeof vis);
// for(int i=1;i<=cr;i++)
// if(!deg[i])q.push(i);
// while(q.size())
// {
// int x=q.front(); q.pop();
// if(b[x])vis[x]=1;
// for(int i=head[x],u;i;i=edge[i].nxt)
// {
// if(col[st]==(u=edge[i].to)&&vis[x]){ans=max(ans,val[x]); continue;}
// if(vis[x])vis[u]=1;
// val[u]+=val[x]; deg[u]--;
// if(!deg[u])q.push(u);
// }
// }
// ans+=val[col[st]];
//}
void spfa()
{
memset(vis,,sizeof vis);
q.push(col[st]); dis[col[st]]=val[col[st]]; vis[col[st]]=;
while(q.size())
{
int x=q.front(); q.pop(); vis[x]=;
for(int i=head[x],u;i;i=edge[i].nxt)
{
if(dis[u=edge[i].to]<dis[x]+val[u])
{
dis[u]=dis[x]+val[u];
if(!vis[u])vis[u]=,q.push(u);
}
}
}
for(int i=;i<=cr;i++)
if(b[i])ans=max(ans,dis[i]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
ed[++ct]=N(y,hd[x]); hd[x]=ct;
}
for(int i=;i<=n;i++)scanf("%d",&a[i]);
scanf("%d%d",&st,&p);
for(int i=,x;i<=p;i++)scanf("%d",&x),bar[x]=;
for(int i=;i<=n;i++) if(!dfn[i])tarjan(i);
for(int i=;i<=n;i++)
for(int j=hd[i],u;j;j=ed[j].nxt)
if(col[u=ed[j].to]!=col[i])
{
edge[++xt]=N(col[u],head[col[i]]); head[col[i]]=xt;
// deg[col[i]]++;
}
// topo();
spfa();
printf("%lld\n",ans);
return ;
}

最新文章

  1. Cesium原理篇:Batch
  2. 在Centos中部署redis运行状态图形化监控工具 — RedisLive
  3. 前端SEO技巧
  4. 利用反射,泛型,静态方法快速获取表单值到Model
  5. Java字符串面试(二)
  6. 【原】IOS中KVO模式的解析与应用
  7. [BZOJ2724][Violet 6]蒲公英
  8. N-Queens | &amp; N-Queens II
  9. 修改后的SQL分页存储过程,利用2分法,支持排序
  10. C#-将控件动态添加到选项卡页tablepage
  11. phpMyAdmin下载与安装
  12. a标签无disabled属性
  13. http://blog.163.com/db_teacher/blog/static/194540298201110723712407/
  14. UITableView 编辑模式(增加-删除-移动---自定义左滑 title)
  15. JAVA描述的简单ORM框架
  16. Centos 7.3 安装Grafana 6.0
  17. C#6.0语言规范(三) 基本概念
  18. (理论篇)从基础文件IO说起虚拟内存,内存文件映射,零拷贝
  19. org.springframework.beans.factory.BeanDefinitionStoreException Invalid bean defi
  20. EF框架搭建小总结--CodeFirst代码优先

热门文章

  1. JS——锚点的运用
  2. Struts2框架实现简单的用户登入
  3. 调用.NET Serviced Component引发的性能问题及其解决
  4. 扩增子图表解读1箱线图:Alpha多样性
  5. VUE路由history模式坑记--NGINX
  6. CentOS安装Nodejs-v8.11.1
  7. Linux 下phpstudy的安装使用补充说明
  8. css的基础知识1
  9. awk 新手入门笔记
  10. HDU - 5894 Pocky(概率)