专栏首页HansBug's Lab1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

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]

Description

每年万圣节,威斯康星的奶牛们都要打扮一番,出门在农场的N(1≤N≤100000)个牛棚里转悠,来采集糖果.她们每走到一个未曾经过的牛棚,就会采集这个棚里的1颗糖果. 农场不大,所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛棚”.牛棚i的后继牛棚是Xi.他告诉奶牛们,她们到了一个牛棚之后,只要再往后继牛棚走去,就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段,来节约他的糖果.  第i只奶牛从牛棚i开始她的旅程.请你计算,每一只奶牛可以采集到多少糖果.

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

Sample Output

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

题解:N个月前刚刚开BZOJ权限的时候,看了这道题,毫无思路,甚至想过暴搜(实际上此题求的就是各点所能到达的点的个数),但是要是 \( N \leq 1000 \) 的话倒还说的过去,\( O({N}^{2} ) \) 的复杂度毕竟。。。

实际上现在做起来也不难,就是个tarjan算法,将复杂图缩点转化为拓扑图,然后慢慢递推即可A掉。。。

  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;
 26 procedure add(x,y:longint;var a:map);
 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
 73      readln(n);
 74      for i:=1 to n do a[i]:=nil;
 75      for i:=1 to n do
 76          begin
 77               readln(j);
 78               add(i,j,a);
 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
 96                          if b[i]<>b[p^.g] then add(b[i],b[p^.g],c);
 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]]);
105      readln;
106 end.      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法模板——Trie树

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

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

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

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

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

    HansBug
  • Java堆

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

    Java学习录
  • 1218: [HNOI2003]激光炸弹

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

    HansBug
  • 《Spring敲门砖之基础教程第一季》 第一章(2)解读Spring Framework

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

    用户1257215
  • 1296: [SCOI2009]粉刷匠

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

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

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

    HansBug
  • Apache Atlas系列 -- 部署

    摘抄一段官网上的介绍,Atlas 是一个可伸缩且功能丰富的数据管理系统,深度集成了 Hadoop 大数据组件。简单理解就是一个跟 Hadoop 关系紧密的,可以...

    runzhliu
  • SAP登陆设置:直接登录所需界面

    matinal

扫码关注云+社区

领取腾讯云代金券