BZOJ 1179 [Apio2009]Atm(强连通分量)

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1179

【题目大意】

  给出一张有向带环点权图,给出一些终点,在路径中同一个点的点权只能累加一次,问从起点到任意终点所能得到的最大点权和。

【题解】

  因为有环,所以一定存在强连通分量,我们将所有环处理成点,在SCC为点的重构图上跑SPFA最长路就可以得到答案。

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=500010,M=500010;
int G[3][N],NXT[3][M<<1],V[3][M<<1],ed=0,f[N],q[N],t,vis[N],n,m,x,y,dp[N],val[N];
void add(int x,int y){
V[0][++ed]=y;NXT[0][ed]=G[0][x];G[0][x]=ed;
V[1][ed]=x;NXT[1][ed]=G[1][y];G[1][y]=ed;
}
void ADD(int x,int y){V[2][++ed]=y;NXT[2][ed]=G[2][x];G[2][x]=ed;}
void dfs1(int x){
vis[x]=1;
for(int i=G[0][x];i;i=NXT[0][i])if(!vis[V[0][i]])dfs1(V[0][i]);
q[++t]=x;
}
void dfs2(int x,int y){
vis[x]=0,f[x]=y;
for(int i=G[1][x];i;i=NXT[1][i])if(vis[V[1][i]])dfs2(V[1][i],y);
}
int h,td,d[N],in[N],i,j;
void spadd(int x,int y){
if(y<=d[x])return;
d[x]=y;
if(!in[x]){
in[x]=1;
if(y>d[q[h]])q[--h]=x;else q[++td]=x;
}
}
void spfa(int S){
int i,x;
for(i=h=1;i<=n;i++)d[i]=val[i],in[i]=0;d[S]=td=0;spadd(S,val[S]);
while(h!=td+1)for(i=G[2][x=q[h++]],in[x]=0;i;i=NXT[2][i])spadd(V[2][i],d[x]+val[V[2][i]]);
}
void R(int&a){
char ch;while(!((ch=getchar())>='0')&&(ch<='9'));
a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
}
int S,P;
int main(){
R(n),R(m);
for(int i=1;i<=m;i++){
R(x);R(y);
add(x,y);
}for(t=0,i=1;i<=n;i++)if(!vis[i])dfs1(i);
for(i=n;i;i--)if(vis[q[i]])dfs2(q[i],q[i]);
for(int i=1;i<=n;i++){scanf("%d",&x);val[f[i]]+=x;}
for(ed=0,i=1;i<=n;i++)for(j=G[0][i];j;j=NXT[0][j])
if(f[i]!=f[V[0][j]])ADD(f[i],f[V[0][j]]);
R(S);R(P); S=f[S]; int ans=0; spfa(S);
for(int i=1;i<=P;i++){R(x);ans=max(ans,d[f[x]]);}
printf("%d\n",ans);
return 0;
}
上一篇:关于IDEA每次修改HTML,Css等静态资源文件都需要重启的设置修改


下一篇:添加并删除Marker