首页 > 代码库 > BZOJ 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
BZOJ 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
Description
每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果． 农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果． 第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．
Input
第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．
Output
共N行，一行一个整数表示一只奶牛可以采集的糖果数量．
题解：
是一个基环树森林，可以用基环树的方法瞎搞。
也可以求强联通分量乱搞。
代码：
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;int H[100005],X[100005],P[100005];int tot;inline void add(int x,int y){ P[++tot]=y;X[tot]=H[x];H[x]=tot;}long long ans[100005];int low[100005];int stk[100005];bool instk[100005];int to[100005];int belong[100005];int hav[100005];int cnt,tim;int top;void tarjan(int x){ int dfn=low[x]=++tim; stk[top++]=x;instk[x]=1; if(!low[to[x]]){ tarjan(to[x]); low[x]=min(low[x],low[to[x]]); }else if(instk[to[x]]) low[x]=min(low[x],low[to[x]]); if(dfn==low[x]){ int k; cnt++; do{ k=stk[--top]; instk[k]=0; belong[k]=cnt; hav[cnt]++; }while(x!=k); }}int ask(int x){ if(ans[x]) return ans[x]; ans[x]=hav[x]; if(hav[x]==1) ans[x]+=ask(P[H[x]]); return ans[x];}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&to[i]); } for(int i=1;i<=n;i++){ if(!low[i]) tarjan(i); } for(int i=1;i<=n;i++){ if(belong[i]!=belong[to[i]]) add(belong[i],belong[to[i]]); } for(int i=1;i<=n;i++){ printf("%d\n",ask(belong[i])); } return 0;}
BZOJ 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。