题解 CF1027D 【Mouse Hunt】

这道题原本写了一个很复杂的DFS，然后陷入绝望的调试。

看了一下题解发现自己完全想复杂了。

这里大概就是补充一些题解没有详细解释的代码吧。。。

（小声BB）现在最优解rank4（话说$O2$负优化什么鬼啊）

 read(n);

 for(register int i=;i<=n;++i)read(c[i]);

 for(register int i=;i<=n;++i){

     read(a[i]);

     if(a[i]==i){

         vis[i]=;

         ans+=c[i];

     }

 }

 for(register int i=;i<=n;++i){

     if(vis[i])continue;

     for(register int j=i;;j=a[j]){

         if(vis[j]){

             if(vis[j]==i+)ans+=find(j);

             break;

         }

         vis[j]=i+;

     }

 }

 write(ans);

程序主题内容如下。

前面是读入数据没有什么好讲的。

在读入a的时候先判断一下有没有自环，有的话就不用看了直接加上。

然后我们对每一个点都瞎搞搞（其实就是一个DFS）。

我们从这个点开始一直向下跳。如果遇到已经走过的点就说明有环出现了，这个时候根据vis的值决定是不是这一轮跳出的环（由于可能是之前的）。

然后我们在这个环上跑一下求最小值。（为什么只在环上不在链上前面题解讲得很清楚了）

如果不是已经走过的点，那我们还在链上，继续往下跳吧。

find函数如下：

 inline int find(int s){

     int res=c[s];

     for(register int i=a[s];;i=a[i]){

         if(i==s)return res;

         else res=min(res,c[i]);

     }

 }

巴特西

题解 CF1027D 【Mouse Hunt】

最新文章

热门文章