bzoj 1179 [Apio2009]Atm——SCC缩点+spfa
2024-08-28 20:01:10
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1179
显然SCC缩点。
然后准备倒着拓扑序推到st,结果WA。
听TJ说dj求最长路会发生不好的事情,于是学TJ用了spfa。
因为是有向边所以别再tarjan里判fa!!!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=5e5+;
int n,m,cnt,hd[N],thd[N],st,ps,rd[N];
int dfn[N],low[N],tim,sta[N],top,col[N];
bool b[N],p[N],r[N],ins[N];
ll c[N],q[N],dis[N],ans;
struct Ed{
int nxt,tnxt,fr,to;
Ed(int n=,int f=,int t=):nxt(n),fr(f),to(t) {tnxt=;}
}ed[N];
void tarjan(int cr)
{
dfn[cr]=low[cr]=++tim;
sta[++top]=cr;ins[cr]=;
for(int i=hd[cr],v;i;i=ed[i].nxt)
if(!dfn[v=ed[i].to])
{
tarjan(v);low[cr]=min(low[cr],low[v]);
}
else if(ins[v])low[cr]=min(low[cr],dfn[v]);
if(dfn[cr]==low[cr])
{
cnt++;
while(sta[top]!=cr)
{
r[cnt]|=p[sta[top]];c[cnt]+=q[sta[top]];
col[sta[top]]=cnt;ins[sta[top--]]=;
}
top--;col[cr]=cnt;ins[cr]=;
r[cnt]|=p[cr];c[cnt]+=q[cr];
}
}
void spfa()
{
dis[col[st]]=c[col[st]];
memset(ins,,sizeof ins);ins[col[st]]=;
queue<int> q;q.push(col[st]);
while(q.size())
{
int k=q.front();q.pop();ins[k]=;
for(int i=thd[k],v;i;i=ed[i].tnxt)
if(dis[k]+c[v=col[ed[i].to]]>dis[v])
{
dis[v]=dis[k]+c[v];
if(!ins[v])ins[v]=,q.push(v);
}
}
}
int main()
{
scanf("%d%d",&n,&m);int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
ed[i]=Ed(hd[x],x,y);hd[x]=i;
}
for(int i=;i<=n;i++)scanf("%lld",&q[i]);
scanf("%d%d",&st,&ps);
for(int i=;i<=ps;i++)
{
scanf("%d",&x);p[x]=;
}
for(int i=;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=,v;i<=m;i++)
if((v=col[ed[i].fr])!=col[ed[i].to])
ed[i].tnxt=thd[v],thd[v]=i;
spfa();
// ed[i].tnxt=thd[v],thd[v]=i,rd[u]++;
// int h=0,t=0;
// for(int i=1;i<=cnt;i++)
// if(!rd[i])sta[++t]=i;
// while(h<=t)
// {
// int k=sta[++h];lj[k]+=c[k];b[k]|=r[k];
// if(!b[k])lj[k]=0;
// for(int i=thd[k],v;i;i=ed[i].tnxt)
// {
// rd[v=col[ed[i].fr]]--;
// lj[v]=max(lj[v],lj[k]);b[v]|=b[k];
// if(!rd[v])sta[++t]=v;
// }
// }
// printf("%lld\n",lj[col[st]]);
for(int i=;i<=cnt;i++)if(r[i])ans=max(ans,dis[i]);
printf("%lld\n",ans);
return ;
}
最新文章
- Android项目实战(二十四):项目包成jar文件,并且将工程中引用的jar一起打入新的jar文件中
- Codeforces Round #279 (Div. 2) vector
- SQL Join的一些总结
- 跳跃表Skip List的原理和实现
- C#时间日期格式大全
- 从scanf的学习接口设计
- IOS webView快照
- UVa 10137 &; ZOJ 1874 The Trip
- Neo4j学习笔记(1)——使用API编写一个Hello World程序
- 实现鼠标hover动画效果自己理解的两种方法——练习笔记
- 勾勾街:用最小的成本封装一个苹果IOS APP! 封装技术再度升级~
- IIS (安装SSL证书后) 实现 HTTP 自动跳转到 HTTPS
- MySQL api
- MDX Step by Step 读书笔记(七) - Performing Aggregation 聚合函数之 Max, Min, Count , DistinctCount 以及其它 TopCount, Generate
- [IR] Word Embeddings
- docker默认ip查询
- python之traceback
- golang slice使用不慎导致的问题
- C#中调用PowerShell代码
- BZOJ4590 Shoi2015 自动刷题机 【二分】