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