题目: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 ;
}

最新文章

  1. Android项目实战(二十四):项目包成jar文件,并且将工程中引用的jar一起打入新的jar文件中
  2. Codeforces Round #279 (Div. 2) vector
  3. SQL Join的一些总结
  4. 跳跃表Skip List的原理和实现
  5. C#时间日期格式大全
  6. 从scanf的学习接口设计
  7. IOS webView快照
  8. UVa 10137 &amp; ZOJ 1874 The Trip
  9. Neo4j学习笔记(1)——使用API编写一个Hello World程序
  10. 实现鼠标hover动画效果自己理解的两种方法——练习笔记
  11. 勾勾街:用最小的成本封装一个苹果IOS APP! 封装技术再度升级~
  12. IIS (安装SSL证书后) 实现 HTTP 自动跳转到 HTTPS
  13. MySQL api
  14. MDX Step by Step 读书笔记(七) - Performing Aggregation 聚合函数之 Max, Min, Count , DistinctCount 以及其它 TopCount, Generate
  15. [IR] Word Embeddings
  16. docker默认ip查询
  17. python之traceback
  18. golang slice使用不慎导致的问题
  19. C#中调用PowerShell代码
  20. BZOJ4590 Shoi2015 自动刷题机 【二分】

热门文章

  1. js 调用接口并传参
  2. .Global.asax.cs中的方法的含义
  3. MyBatis与Hibernate
  4. 杜教筛&amp;套路总结
  5. call和apply的应用
  6. LOJ10157——皇宫看守(树形DP)
  7. Ubuntu 安装gnome桌面及vnc远程连接
  8. python面向对象应用-1
  9. linux中断处理-顶半部(top half)和底半部(bottom half) -转
  10. 在ALV点击Key值调用TCode,跳过初始屏幕