【强连通分量+spfa】Bzoj1179 Apio2009 Atm
2024-08-26 15:38:44
Description
Solution
显然缩强连通分量,然后求最长路,虽然是DAG但还是有点麻烦,于是用了spfa。
Code
重建图_数组写错好多次,感觉做这题也就是练了一下实现。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e+; int pre[maxn],low[maxn],clock;
int scc[maxn],val[maxn],cnt,a[maxn],t;
int head[maxn],f[maxn],e[maxn],nxt[maxn],k;
int adde(int u,int v){
f[++k]=u,e[k]=v;
nxt[k]=head[u],head[u]=k;
}
int n,m,s,p;
int w[maxn],ok[maxn]; int dfs(int u){
//printf("%d\n",u);
pre[u]=low[u]=++clock;
a[++t]=u;
for(int i=head[u];i;i=nxt[i]){
int v=e[i];
if(!pre[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!scc[v]){
low[u]=min(low[u],pre[v]);
}
}
if(low[u]==pre[u]){
++cnt;
while(t){
scc[a[t]]=cnt;
val[cnt]+=w[a[t]];
if(a[t--]==u) break;
}
}
} int ok_[maxn];
int head_[maxn],e_[maxn],nxt_[maxn],k_;
int adde_(int u,int v){
e_[++k_]=v;
nxt_[k_]=head_[u],head_[u]=k_;
} int rebuild(){
for(int i=;i<=k;i++){
int u=scc[f[i]],v=scc[e[i]];
if(u!=v) adde_(u,v);
}
for(int i=;i<=n;i++)
if(ok[i]) ok_[scc[i]]=;
} int q[maxn],d[maxn],inque[maxn],ans,h;
int spfa(){
t=;
s=scc[s];
q[++t]=s;
inque[s]=;
d[s]=val[s];
ans=d[s];
while(h<t){
int u=q[++h];
//printf("%d\n",u);
for(int i=head_[u];i;i=nxt_[i]){
int v=e_[i];
if(d[u]+val[v]>d[v]){
//printf(" %d\n",v);
d[v]=d[u]+val[v];
if(ok_[v]) ans=max(ans,d[v]);
if(!inque[v]) inque[v]=,q[++t]=v;
}
}
inque[u]=;
}
} int main(){
scanf("%d%d",&n,&m);
int u,v,x;
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
adde(u,v);
}
for(int i=;i<=n;i++)
scanf("%d",&w[i]);
scanf("%d%d",&s,&p);
for(int i=;i<=p;i++)
scanf("%d",&x),ok[x]=; for(int i=;i<=n;i++)
if(!pre[i]) dfs(i); rebuild();
spfa();
printf("%d\n",ans);
return ;
}
最新文章
- IOS系列swift语言之课时二
- Generator库co4.6使用及源码分析
- 第一、初识C语言
- Hibernate笔记——第一个简单实例
- Castle ActiveRecord简单介绍
- BZOJ2870: 最长道路tree
- ST-Link 驱动安装
- Oracle core02_数据块
- 在Ubuntu下搭建FTP服务器的方法
- angular 4使用jquery 第三方插件库
- FPGA时钟分频(转)
- EF获取多个数据集以及MySQL分页数据查询优化
- 利用sqlalchemy读取数据库 和pandas的Dataframe对象 互相生成
- SpringBoot Web开发(5) 开发页面国际化+登录拦截
- squid代理http和https方式上网的操作记录
- JS的浅拷贝与深拷贝
- 假如java类里的成员变量是自身的对象
- memcached全面剖析--4. memcached的分布式算法
- java,arduino,C#之间的一些编码转换
- EBS中比较复杂的trace方法