P2921 [USACO08DEC]在农场万圣节[SCC缩点]

P2921 [USACO08DEC]在农场万圣节[SCC缩点]

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

解析

警告：非正解玄学AC。

看到这道题tag，想了半天记搜也想不出来，差点砸电脑，索性缩点。

显然，一个SCC里所有点的答案是相同的，于是我们将原图缩点，得到一个类似链状DAG的东西，然后我们就要考虑如何统计其它点到这些SCC经过的点，显然一个dfs就搞定了。不过我的处理方法可能有点玄学，具体看代码。

参考代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define N 200010
using namespace std;
inline int read()
{int f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
struct rec{int next,ver;
}g[N],G[N];
int head[N],headG[N],tot,totG,idt,c[N],n,cnt,dfn[N],low[N];
int stack[N],top,scc[N],ans[N];
bool ins[N],v[N];
inline void add(int x,int y)
{g[++tot].ver=y;g[tot].next=head[x],head[x]=tot;
}
inline void addG(int x,int y)
{G[++totG].ver=y;G[totG].next=headG[x],headG[x]=totG;
}
inline void tarjan(int x)//求SCC 
{dfn[x]=low[x]=++cnt;stack[++top]=x,ins[x]=1;for(int i=head[x];i;i=g[i].next){int y=g[i].ver;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(ins[y]) low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){int y;++idt;do{y=stack[top--],ins[y]=0;c[y]=idt;scc[idt]++;}while(x!=y);}
}
inline void dfs(int x)
{v[x]=1;ans[x]=1;for(int i=head[x];i;i=g[i].next){int y=g[i].ver;if(x==y) continue;//一个点需要特判 if(scc[c[y]]>1){ans[x]+=scc[c[y]];//如果下一个点是一个SCC，特判一下 return;}if(v[y]){ans[x]+=ans[y];continue;//如果直接continue这个点的ans就加不上了 }v[y]=1;dfs(y);ans[x]+=ans[y];//回溯更新节点 }
}
int main()
{n=read();for(int i=1;i<=n;++i){int to;to=read();add(i,to);}for(int i=1;i<=n;++i)if(!dfn[i]) tarjan(i);for(int x=1;x<=idt;++x)for(int i=head[x];i;i=g[i].next){int y=g[i].ver;if(c[x]==c[y]) continue;addG(c[x],c[y]);}for(int i=1;i<=n;++i)if(!v[i]&&scc[c[i]]==1) dfs(i);//对除SCC的点进行统计 for(int i=1;i<=n;++i){if(scc[c[i]]>1) printf("%dn",scc[c[i]]);//SCC中的某点能到达的点数就是整个SCC包含的点数 else printf("%dn",ans[i]);}return 0;
}

转载于:.html