题目：

伯兰州立大学的医学部刚刚结束了招生活动。和以往一样，约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]连边

代码：

#include<cstdio>
#include<stack>
using namespace std;
int a[200005];
int cnt=0;
int vis[200005],c[200005];
int flag;
int tag;
stack<int>s;
void dfs(int x)
{
    if(a[x]==0)
    {
        return ;
    }
    cnt++;
    if(cnt>vis[x]&&vis[x])
    {
        flag=1;
        tag=x;
        a[x]=0;
        vis[x]=0;
        return ;
    }
    s.push(x);
    vis[x]=cnt;
    dfs(a[x]);
    vis[x]=0;
    a[x]=0;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        while(!s.empty())s.pop();
        flag=0;
        dfs(i);
        if(flag)
        {
            int ans=2147483647;
            if(!s.empty())
            {
                while(!s.empty()&&s.top()!=tag)
                {
                    ans=min(ans,c[s.top()]);
                    s.pop();
                }
                if(!s.empty())
                ans=min(ans,c[s.top()]);
                sum+=ans;
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}

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