在农场万圣节-白红宇

在农场万圣节

阅读量：4332 次

发布时间：2019-06-06

本文共 1006 字，大约阅读时间需要 3 分钟。

大体理解了思路，经常复习复习，不要忘了。

因为每个点的出度只有1，那么每个点向下走的路径是唯一的。

题解里说的两种情况

enter image description here

代码：

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 200005;int n,net[N],color[N],sucdfn[N],dfn[N],minc[N];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)      scanf("%d",&net[i]);    for(int cow=1;cow<=n;++cow)    {        int cnt=0;        for(int i=cow;;i=net[i])        {            if(!color[i])            {                color[i]=cow;                dfn[i]=cnt;            }            else if(color[i]==cow)            {                minc[cow]=cnt-dfn[i];                sucdfn[cow]=dfn[i];                printf("%d\n",cnt);                break;            }            else             {                minc[cow]=minc[color[i]];                sucdfn[cow]=cnt+max(sucdfn[color[i]]-dfn[i],0);                printf("%d\n",sucdfn[cow]+minc[cow]);                break;             }            ++cnt;        }    }}

转载于:https://www.cnblogs.com/karryW/p/11396870.html

你可能感兴趣的文章

敏捷开发中软件测试团队的职责和产出是什么？

查看>>

在mvc3中使用ffmpeg对上传视频进行截图和转换格式

查看>>