欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforce round#49D---Mouse Hunt

程序员文章站 2022-04-02 22:09:32
...

codeforce round#49D---Mouse Hunt

可以将题目转化为一个图,每个节点只有一个出度,对于入度为0的点,如果在该点放陷阱,则必须再次在其后继节点放,因而有了额外的花费;不断去掉入度为0的节点后发现最后剩下的一定是一个环,而且不可能是叠加环(因为每个节点出度为1),这时候只需要处理每一个环即可,即取环中花费最小的节点安放陷阱

#include<cstdio>
#include<queue>
using namespace std;
const int n_max=2e5+5;
int idegree[n_max],cost[n_max],trans[n_max];
int main()
{
    int n;
    queue<int>q;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&cost[i]);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&trans[i]);
        ++idegree[trans[i]];
    }
    for(int i=1;i<=n;++i)
    {
        if(idegree[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        --idegree[trans[x]];
        if(idegree[trans[x]]==0)
            q.push(trans[x]);
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        if(idegree[i]!=0)
        {
            int temp=cost[i],u=trans[i];
            idegree[i]=0;
            while(idegree[u]!=0)
            {
                temp=min(temp,cost[u]);
                idegree[u]=0;
                u=trans[u];
            }
            ans+=temp;
        }
    }
    printf("%d\n",ans);
}

 

相关标签: 思维