伯兰州立大学的医学部刚刚结束了招生活动。和以往一样，约80%的申请人都是女生并且她们中的大多数人将在未来4年（真希望如此）住在大学宿舍里。

宿舍楼里有nn个房间和一只老鼠！女孩们决定在一些房间里设置捕鼠器来除掉这只可怕的怪物。在ii号房间设置陷阱要花费c_ic
i
​ 伯兰币。房间编号从11到nn。

要知道老鼠不是一直原地不动的，它不停地跑来跑去。如果tt秒时它在ii号房间，那么它将在t+1t+1秒时跑到a_ia
i
​ 号房间，但这期间不会跑到别的任何房间里(i=a_ii=a
i
​ 表示老鼠没有离开原来的房间)。时间从00秒开始，一旦老鼠窜到了有捕鼠器的房间里，这只老鼠就会被抓住。

如果女孩们知道老鼠一开始在哪里不就很容易吗？不幸的是，情况不是这样，老鼠在第00秒时可能会在从11到nn的任何一个房间内。

那么女孩们最少要花多少钱设置捕鼠器，才能保证老鼠无论从哪个房间开始流窜最终都会被抓到？

stack解决

a向a[x]连边

  1. #include<cstdio>
  2. #include<stack>
  3. using namespace std;
  4. int a[200005];
  5. int cnt=0;
  6. int vis[200005],c[200005];
  7. int flag;
  8. int tag;
  9. stack<int>s;
  10. void dfs(int x)
  11. {
  12.     if(a[x]==0)
  13.     {
  14.         return ;
  15.     }
  16.     cnt++;
  17.     if(cnt>vis[x]&&vis[x])
  18.     {
  19.         flag=1;
  20.         tag=x;
  21.         a[x]=0;
  22.         vis[x]=0;
  23.         return ;
  24.     }
  25.     s.push(x);
  26.     vis[x]=cnt;
  27.     dfs(a[x]);
  28.     vis[x]=0;
  29.     a[x]=0;
  30. }
  31. int main()
  32. {
  33.     int n;
  34.     scanf("%d",&n);
  35.     for(int i=1;i<=n;i++)
  36.     {
  37.         scanf("%d",&c[i]);
  38.     }
  39.     for(int i=1;i<=n;i++)
  40.     {
  41.         scanf("%d",&a[i]);
  42.     }
  43.     int sum=0;
  44.     for(int i=1;i<=n;i++)
  45.     {
  46.         while(!s.empty())s.pop();
  47.         flag=0;
  48.         dfs(i);
  49.         if(flag)
  50.         {
  51.             int ans=2147483647;
  52.             if(!s.empty())
  53.             {
  54.                 while(!s.empty()&&s.top()!=tag)
  55.                 {
  56.                     ans=min(ans,c[s.top()]);
  57.                     s.pop();
  58.                 }
  59.                 if(!s.empty())
  60.                 ans=min(ans,c[s.top()]);
  61.                 sum+=ans;
  62.             }
  63.         }
  64.     }
  65.     printf("%d\n",sum);
  66.     return 0;
  67. }

版权声明：本文为ShineEternal原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ShineEternal/p/11222478.html