题解:
首先第一个阶段,
可以写kosaraju、也可以写tarjan。
这两种还都分递归和dfs转非递归。
----------------------------------四种方案。
第二个阶段,可以写拓扑DP
也可以写最长路
----------------------------------乘上之前的,,八种方案。
本文写了kosaraju递归版,tarjan递归版,kosaraju非递归版。
……只怪学校oj系统栈太小。。都是逼得啊。
代码1(tarjan):
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 501000 using namespace std; struct KSD { int u,v,next; }e[N],E[N]; int head[N],cnt,Head[N]; void add(int u,int v) { cnt++; e[cnt].u=u; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void Add(int u,int v) { cnt++; E[cnt].v=v; E[cnt].next=Head[u]; Head[u]=cnt; } int dfn[N],low[N]; int group,id[N]; bool in[N]; int stk[N],top; int fee[N],Fee[N]; bool Bar[N],bar[N]; void tarjan(int x) { dfn[x]=low[x]=++cnt; stk[++top]=x,in[x]=1; for(int i=head[x];i;i=e[i].next) { if(!dfn[e[i].v]) { tarjan(e[i].v); low[x]=min(low[x],low[e[i].v]); } else if(in[e[i].v])low[x]=min(low[x],dfn[e[i].v]); } if(low[x]==dfn[x]) { group++; do{ in[stk[top]]=0,id[stk[top]]=group; Fee[group]+=fee[stk[top]]; Bar[group]|=bar[stk[top]]; }while(stk[top--]!=x); } } int n,m,s,p; bool ok[N]; void bfs() { int i,u,v; stk[top=1]=s; while(top) { u=stk[top--]; ok[u]=1; for(i=head[u];i;i=e[i].next) { v=e[i].v; if(!ok[v])stk[++top]=v; } } } int dp[N],d[N]; int main() { // freopen("test.in","r",stdin); int i,j,k; int a,b,c; int u,v; scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d",&a,&b),add(a,b); for(i=1;i<=n;i++)scanf("%d",&fee[i]); scanf("%d%d",&s,&p); for(i=1;i<=p;i++)scanf("%d",&c),bar[c]=true; for(c=cnt,cnt=0,i=1;i<=n;i++)if(!dfn[i])tarjan(i); bfs(); for(cnt=0,i=1;i<=c;i++) { if((!ok[e[i].u])||(!ok[e[i].v]))continue; a=id[e[i].u],b=id[e[i].v]; if(a==b)continue; Add(a,b); d[b]++; } stk[top=1]=id[s]; int ans=0; while(top) { u=stk[top--]; if(Bar[u])ans=max(ans,dp[u]+Fee[u]); for(i=Head[u];i;i=E[i].next) { v=E[i].v; dp[v]=max(dp[v],dp[u]+Fee[u]); d[v]--; if(!d[v])stk[++top]=v; } } printf("%d\n",ans); return 0; }
代码2(kosaraju):
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 501000 using namespace std; struct KSD { int u,v,next; }e[N],ez[N]; int head[N],lux[N],cnt; inline void add(int u,int v) { cnt++; ez[cnt].v=e[cnt].u=u; e[cnt].v=v; ez[cnt].next=lux[v]; e[cnt].next=head[u]; head[u]=lux[v]=cnt; } inline void add2(int u,int v) { cnt++; ez[cnt].v=v; ez[cnt].next=lux[u]; lux[u]=cnt; } bool vis[N]; int dfn[N],top; int id[N],group; int n,m,s,p; int fee[N]; bool bar[N]; int Fee[N]; bool Bar[N]; void dfs1(int x) { vis[x]=1; for(int i=head[x];i;i=e[i].next)if(!vis[e[i].v])dfs1(e[i].v); dfn[++top]=x; } void dfs2(int x) { id[x]=group; Bar[group]|=bar[x]; Fee[group]+=fee[x]; for(int i=lux[x];i;i=ez[i].next)if(!id[ez[i].v])dfs2(ez[i].v); } int d[N],dp[N]; bool ok[N]; void bfs() { int i,u,v; dfn[top=1]=s; while(top) { u=dfn[top--]; ok[u]=1; for(i=head[u];i;i=e[i].next) { v=e[i].v; if(!ok[v])dfn[++top]=v; } } } int main() { // freopen("test.in","r",stdin); int i,j,k; int a,b,c; scanf("%d%d",&n,&m); while(m--)scanf("%d%d",&a,&b),add(a,b); for(i=1;i<=n;i++)scanf("%d",&fee[i]); scanf("%d%d",&s,&p); while(p--)scanf("%d",&c),bar[c]=true; bfs(); for(i=1;i<=n;i++)if(!vis[i])dfs1(i); for(i=top;i;i--)if(!id[dfn[i]])group++,dfs2(dfn[i]); memset(lux,0,sizeof(lux)); c=cnt,cnt=0; for(i=1;i<=c;i++) { if(!ok[e[i].u])continue; a=id[e[i].u],b=id[e[i].v]; if(a==b)continue; add2(a,b); d[b]++; } dfn[top=1]=id[s]; int ans=0; while(top) { a=dfn[top--]; if(Bar[a])ans=max(ans,dp[a]+Fee[a]); for(i=lux[a];i;i=ez[i].next) { c=ez[i].v; dp[c]=max(dp[c],dp[a]+Fee[a]),d[c]--; if(!d[c])dfn[++top]=c; } } printf("%d\n",ans); return 0; }
代码3(kosaraju+主要部分转非递归):
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 501000 using namespace std; struct KSD { int u,v,next; }e[N],ez[N]; int head[N],lux[N],cnt; inline void add(int u,int v) { cnt++; ez[cnt].v=e[cnt].u=u; e[cnt].v=v; ez[cnt].next=lux[v]; e[cnt].next=head[u]; head[u]=lux[v]=cnt; } inline void add2(int u,int v) { cnt++; ez[cnt].v=v; ez[cnt].next=lux[u]; lux[u]=cnt; } bool vis[N]; int dfn[N],top; int id[N],group; int n,m,s,p; int fee[N]; bool bar[N]; int Fee[N]; bool Bar[N]; int stk[N]; int which[N]; inline void dfs1(int x) { int i,u,v; vis[x]=1; which[x]=head[x]; stk[top=1]=x; while(top) { u=stk[top]; i=which[u]; if(!i) { top--; dfn[++cnt]=u; continue; } if(!vis[v=e[i].v]) { vis[v]=1; which[v]=head[v]; stk[++top]=v; } which[u]=e[i].next; } }/* ***************************************这个注释部分的dfs转非递归写挂了 inline void dfs2(int x) { int i,u,v; stk[top=1]=x; group++; while(top) { u=stk[top--]; id[u]=group; Bar[group]|=bar[u]; Fee[group]+=fee[u]; for(i=lux[u];i;i=ez[i].next) if(!id[v=ez[i].v]) stk[++top]=v; } }*/ void dfs2(int x) { id[x]=group; Bar[group]|=bar[x]; Fee[group]+=fee[x]; for(int i=lux[x];i;i=ez[i].next)if(!id[ez[i].v])dfs2(ez[i].v); } int d[N],dp[N]; bool ok[N]; void bfs() { int i,u,v; dfn[top=1]=s; while(top) { u=dfn[top--]; ok[u]=1; for(i=head[u];i;i=e[i].next) { v=e[i].v; if(!ok[v])dfn[++top]=v; } } } int main() { // freopen("test.in","r",stdin); int i,j,k; int a,b,c; scanf("%d%d",&n,&m); while(m--)scanf("%d%d",&a,&b),add(a,b); for(i=1;i<=n;i++)scanf("%d",&fee[i]); scanf("%d%d",&s,&p); while(p--)scanf("%d",&c),bar[c]=true; c=cnt,cnt=0; bfs(); for(cnt=0,i=1;i<=n;i++)if(!vis[i])dfs1(i); for(cnt=0,i=n;i;i--)if(!id[dfn[i]])group++,dfs2(dfn[i]); memset(lux,0,sizeof(lux)); for(cnt=0,i=1;i<=c;i++) { if(!ok[e[i].u])continue; a=id[e[i].u],b=id[e[i].v]; if(a==b)continue; add2(a,b); d[b]++; } dfn[top=1]=id[s]; int ans=0; while(top) { a=dfn[top--]; if(Bar[a])ans=max(ans,dp[a]+Fee[a]); for(i=lux[a];i;i=ez[i].next) { c=ez[i].v; dp[c]=max(dp[c],dp[a]+Fee[a]),d[c]--; if(!d[c])dfn[++top]=c; } } printf("%d\n",ans); return 0; }
【BZOJ1179】【Apio2009】Atm 强连通分量缩点+拓扑DP/拓扑最长路 kosaraju+tarjan+dfs转非递归三种代码