并查集/DFS-CodeForces 1027D-Mouse Hunt

淩亂°似流年 2022-05-15 12:09 159阅读 0赞

*  # 并查集/DFS-CodeForces 1027D-Mouse Hunt #

--------------------

*  ## 题目链接： ##

### [D. Mouse Hunt][] ###

*  ## 题目基础：并查集 ##

### [数据结构-并查集][-] ###

*  ## 思路： ##

### 题目大意： ###

给定两个N长度序列，第一个序列表示在每个房间安装捕鼠器的成本，第二个序列是状态图，***表示在第 i 个房间的老鼠，下一秒会去到房间 Next\_Room\[i\] （可以选择停留在该房间）***，求出一定能捉到老鼠的最小成本

### 题解： ###

怎样放捕鼠器才能让老鼠一定被捉到？其实就是放在老鼠在房间中活动形成的环路，想要最小成本，**在每个环中选出安装捕鼠器成本最低的房间**

那要怎么检查老鼠活动是否成环？用到并查集，如果**检查的两个元素在一个集合中，说明成环（两种成环状态，自环-当老鼠停留在原来房间，或者多房间成环）**

然后用***深搜找出每个环安装捕鼠器的最小成本***

*  ### 代码： ###

#include<bits/stdc++.h>
    using namespace std;
    #define MAX_SIZE 200005
    int Node[MAX_SIZE];
    int Height[MAX_SIZE];
    int Burles[MAX_SIZE];
    int Next_Room[MAX_SIZE];
    int Judge[MAX_SIZE];
    void Init(int n)   //初始化结点
    {
        for(int i=0;i<=n;i++)
        {
            Node[i]=-1;
            Height[i]=0;
            Judge[i]=0;
        }
    }
    
    int Find(int x)   //查找集合根
    {
        if(Node[x]==-1)
            return x;
        else
            return Node[x]=Find(Node[x]); //查找到x的根时，将x直接连到根
    }
    
    int Combine(int a,int b)   //a b 符合某种关系需合并，如果a b本同属一个集合，返回0
    {
        int a_root=Find(a);
        int b_root=Find(b);
        if(a_root==b_root)
            return 0;
        if(Height[a_root]<Height[b_root])   //小树a放在b下
            Node[a_root]=b_root;
        else
        {
            Node[b_root]=a_root;
            if(Height[a_root]==Height[b_root])
                Height[a_root]++;
        }
        return 1;
    }
    int DFS(int x,int y)
    {
        if(x==y)
            return Burles[x];
    
        return min(DFS(Next_Room[x],y),Burles[x]);
    }
    
    int main()
    {
        int n;
        int Res=0;
        cin>>n;
        Init(n);
        for(int i=1;i<=n;i++)
            scanf("%d",&Burles[i]);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&Next_Room[i]);
            if(!Combine(i,Next_Room[i]))   //两个房间已在集合内，说明有成环情况，标记
                Judge[i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(Judge[i])
                Res+=DFS(Next_Room[i],i);
        }
        cout<<Res<<endl;
        return 0;
    }

[D. Mouse Hunt]: http://codeforces.com/problemset/problem/1027/D
[-]: https://blog.csdn.net/SZU_Crayon/article/details/81986258