首页 > 代码库 > bzoj1179 [Apio2009]Atm
bzoj1179 [Apio2009]Atm
先进行一次Tarjan缩点变成一个DAG,然后记忆化搜索f[i]=f[j]+v[i]((i,j)∈E)。
#include<cstdio> #include<cctype> #include<vector> #include<algorithm> using namespace std; inline int read(){ char c; while(c=getchar(),!isdigit(c)); int x=c-‘0‘; while(c=getchar(),isdigit(c)) x=x*10+c-‘0‘; return x; } const int maxn=500001; vector<int> e[maxn],e_[maxn]; int n,m,yes[maxn],vis[maxn],val[maxn],v[maxn],scc,f[500001],low[500001],dfn[500001],s[500001],tme,top; void tarjan(int o){ s[++top]=o; low[o]=dfn[o]=++tme; for(int i=0;i<e[o].size();i+=1) if(!vis[e[o][i]]){ if(!low[e[o][i]]) tarjan(e[o][i]); low[o]=min(low[e[o][i]],low[o]); } if(dfn[o]==low[o]){ ++scc; do{ vis[s[top]]=scc; val[scc]+=v[s[top]]; }while(s[top--]!=o); } } void tarjan_work(){ for(int i=1;i<=n;i+=1) if(!low[i]) tarjan(i); for(int i=1;i<=n;i+=1) for(int j=0;j<e[i].size();j+=1) if(vis[i]!=vis[e[i][j]]) e_[vis[i]].push_back(vis[e[i][j]]); } int dfs(int o){ if(f[o]) return yes[o]; f[o]=val[o]; for(int i=0;i<e_[o].size();i+=1) if(dfs(e_[o][i])) yes[o]=1,f[o]=max(f[e_[o][i]]+val[o],f[o]); return yes[o]; } int main(){ n=read(),m=read(); while(m--){ int u=read(),v=read(); e[u].push_back(v); } for(int i=1;i<=n;i+=1) v[i]=read(); tarjan_work(); int s=read(),p=read(); while(p--){ int x=read(); yes[vis[x]]=1; } dfs(vis[s]); printf("%d\n",f[vis[s]]); return 0; }
bzoj1179 [Apio2009]Atm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。