并查集/DFS-CodeForces 1027D-Mouse Hunt
D. Mouse Hunt
数据结构-并查集
题目大意：
给定两个N长度序列，第一个序列表示在每个房间安装捕鼠器的成本，第二个序列是状态图，表示在第 i 个房间的老鼠，下一秒会去到房间 Next_Room[i] （可以选择停留在该房间），求出一定能捉到老鼠的最小成本
题解：
怎样放捕鼠器才能让老鼠一定被捉到？其实就是放在老鼠在房间中活动形成的环路，想要最小成本，在每个环中选出安装捕鼠器成本最低的房间
那要怎么检查老鼠活动是否成环？用到并查集，如果检查的两个元素在一个集合中，说明成环（两种成环状态，自环-当老鼠停留在原来房间，或者多房间成环）
然后用深搜找出每个环安装捕鼠器的最小成本
代码：
include
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;elsereturn 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;
}
古城微笑少年丶
港控/mmm°
Myth丶恋晨
淩亂°似流年
还没有评论，来说两句吧...