# 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

## 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 419  Solved: 232

[Submit][Status][Discuss]

## Input

第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．

## Output

共N行，一行一个整数表示一只奶牛可以采集的糖果数量．

## Sample Input

4 //有四个点 1 //1有一条边指向1 3 //2有一条边指向3 2 //3有一条边指向2 3 INPUT DETAILS: Four stalls. * Stall 1 directs the cow back to stall 1. * Stall 2 directs the cow to stall 3 * Stall 3 directs the cow to stall 2 * Stall 4 directs the cow to stall 3

1 2 2 3

## HINT

Cow 1: Start at 1, next is 1. Total stalls visited: 1. Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.

## Source

Gold

  1 /**************************************************************
2     Problem: 1589
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:716 ms
7     Memory:7324 kb
8 ****************************************************************/
9
10 type
11     point=^node;
12     node=record
13                g:longint;
14                next:point;
15     end;
16     map=array[0..100000] of point;
17 var
18    i,j,k,l,m,n,h,t,ans:longint;
19    low,dfn,f,b,d,e:array[0..100000] of longint;
20    a,c:map;p:point;
21    ss,s:array[0..100000] of boolean;
22 function min(x,y:longint):longint;
23          begin
24               if x<y then min:=x else min:=y;
25          end;
27           var p:point;
28           begin
29                new(p);p^.g:=y;
30                p^.next:=a[x];a[x]:=p;
31           end;
32 procedure tarjan(x:longint);
33           var p:point;
34           begin
35                inc(h);low[x]:=h;dfn[x]:=h;
36                inc(t);f[t]:=x;
37                ss[x]:=true;s[x]:=true;
38                p:=a[x];
39                while p<>nil do
40                      begin
41                           if not(s[p^.g]) then
42                              begin
43                                   tarjan(p^.g);
44                                   low[x]:=min(low[x],low[p^.g]);
45                              end
46                           else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]);
47                           p:=p^.next;
48                      end;
49                if low[x]=dfn[x] then
50                   begin
51                        inc(ans);
52                        while f[t+1]<>x do
53                              begin
54                                   ss[f[t]]:=false;
55                                   b[f[t]]:=ans;
56                                   dec(t);
57                              end;
58                   end;
59           end;
60 procedure dfs(x:longint);
61           var p:point;
62           begin
63                p:=c[x];
64                e[x]:=d[x];
65                while p<>nil do
66                      begin
67                           if e[p^.g]=0 then dfs(p^.g);
68                           e[x]:=e[x]+e[p^.g];
69                           p:=p^.next;
70                      end;
71           end;
72 begin
74      for i:=1 to n do a[i]:=nil;
75      for i:=1 to n do
76          begin
79          end;
80      fillchar(s,sizeof(s),false);
81      fillchar(ss,sizeof(ss),false);
82      fillchar(low,sizeof(low),0);
83      fillchar(dfn,sizeof(dfn),0);
84      fillchar(f,sizeof(f),0);
85      h:=0;t:=0;ans:=0;
86      for i:=1 to n do
87          if b[i]=0 then tarjan(i);
88      fillchar(d,sizeof(d),0);
89      for i:=1 to n do inc(d[b[i]]);
90      for i:=1 to ans do c[i]:=nil;
91      for i:=1 to n do
92          begin
93               p:=a[i];
94               while p<>nil do
95                     begin
97                          p:=p^.next;
98                     end;
99          end;
100      fillchar(e,sizeof(e),0);
101      for i:=1 to ans do
102          if e[i]=0 then dfs(i);
103      for i:=1 to n do
104          writeln(e[b[i]]);
106 end.      

0 条评论

• ### 算法模板——Trie树

实现功能——实现对于不同字符串以及之前出现过的字符串的识别，对于单个长度为L的字符串，复杂度为O(L); 代码不难懂，直接上（在识别字符串方面，个人觉得其好处远...

• ### 1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

1638: [Usaco2007 Mar]Cow Traffic 奶牛交通 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

• ### 算法模板——KMP字符串匹配

功能：输入一个原串，再输入N个待匹配串，在待匹配串中找出全部原串的起始位置 原理：KMP算法，其实这个东西已经包含了AC自动机的思想（fail指针/数组），只不...

• ### Java堆

Java 堆是被所有线程共享的一块内存区域，在虚拟机启动时创建。这个区域是用来存放对象实例的，几乎所有对象实例都会在这里分配内存。平常我们听说的垃圾收集、GC等...

• ### 1218: [HNOI2003]激光炸弹

1218: [HNOI2003]激光炸弹 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1139  Solv...

• ### 《Spring敲门砖之基础教程第一季》 第一章（2）解读Spring Framework

系统架构 一个成功的项目离不开一个好的架构，一个好的架构自然需要一位好的设计师， Rod Johnson正是Spring的前生总架构设计师，那...

• ### 1296: [SCOI2009]粉刷匠

1296: [SCOI2009]粉刷匠 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 916  Solved...

• ### 1592: [Usaco2008 Feb]Making the Grade 路面修整

1592: [Usaco2008 Feb]Making the Grade 路面修整 Time Limit: 10 Sec  Memory Limit: 162...