P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 inline  int read(){
 4     int sum=0,x=1;
 5     char ch=getchar();
 6     while(ch<'0'||ch>'9'){
 7         if(ch=='-')
 8             x=0;
 9         ch=getchar();
10     }
11     while(ch>='0'&&ch<='9')
12         sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
13     return x?sum:-sum;
14 }
15 inline void write(int x){
16     if(x<0)
17         putchar('-'),x=-x;
18     if(x>9)
19         write(x/10);
20     putchar(x%10+'0');
21 }
22 const int M=1e5+5;
23 int nex[M];
24 int color[M];//在图上记录走过的标记；
25 int dfn[M];//时间戳
26 int minc[M];//记录当前换的大小；
27 int incycle[M];//记录当前牛什么时候进入环
28 int ma(int x,int y){
29     return x>y?x:y;
30 }
31 int main(){
32     int n=read();
33     for(int i=1;i<=n;i++)
34         nex[i]=read();
35     for(int i=1;i<=n;i++){
36         for(int j=i,cnt=0;;cnt++,j=nex[j]){
37             if(!color[j]){
38                 color[j]=i;
39                 dfn[j]=cnt;
40             }
41             else if(color[j]==i){
42                 write(cnt);
43                 putchar('
');
44                 minc[i]=cnt-dfn[j];
45                 incycle[i]=dfn[j];
46                 break;
47             }
48             else{
49                 minc[i]=minc[color[j]];
50                 incycle[i]=cnt+ma(incycle[color[j]]-dfn[j],0);
51                 write(minc[i]+incycle[i]);
52                 putchar('
');
53                 break;
54             }
55         }
56     }
57     return 0;
58 }
View Code