D. Mouse Hunt -codeforces -csdn博客
Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80% of applicants are girls and majority of them are going to live in the university dormitory for the next 4 (hopefully) years.
The dormitory consists of n rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number i costs ci burles. Rooms are numbered from 1 to n.
Mouse doesn’t sit in place all the time, it constantly runs. If it is in room i in second t then it will run to room ai in second t+1 without visiting any other rooms inbetween (i=ai means that mouse won’t leave room i). It’s second 0 in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.
That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that’s not the case, mouse can be in any room from 1 to n at second 0.
What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?
Input
The first line contains as single integers n (1≤n≤2⋅105) — the number of rooms in the dormitory.
The second line contains n integers c1,c2,…,cn (1≤ci≤104) — ci is the cost of setting the trap in room number i.
The third line contains n integers a1,a2,…,an (1≤ai≤n) — ai is the room the mouse will run to the next second after being in room i.
Output
Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.
Examples
inputCopy
5
1 2 3 2 10
1 3 4 3 3
outputCopy
3
inputCopy
4
1 10 2 10
2 4 2 2
outputCopy
10
inputCopy
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
outputCopy
2
Note
In the first example it is enough to set mouse trap in rooms 1 and 4. If mouse starts in room 1 then it gets caught immideately. If mouse starts in any other room then it eventually comes to room 4.
In the second example it is enough to set mouse trap in room 2. If mouse starts in room 2 then it gets caught immideately. If mouse starts in any other room then it runs to room 2 in second 1.
Here are the paths of the mouse from different starts from the third example:1→2→2→…;2→2→…;3→2→2→…;4→3→2→2→…;5→6→7→6→…;6→7→6→;7→6→7→…;
So it’s enough to set traps in rooms 2 and 6.
题意：有n个房间，和一只老鼠。现在要用捕鼠器抓这只老鼠。老鼠在时刻t=0在随意的一间房子，每过一个时间，就会跑到另一间房子。跑的房子是在第三行给的数组中。现在要抓到老鼠，在一些房间放捕鼠器，在不同房间方捕鼠器的花费在第二行给的数组中，求抓到老鼠的最小花费。
解题思路：直接从头到尾遍历一下房间，当房间为被访问过（我数组f判断）时，用一个dfs模拟老鼠跑的房间。具体操作细节，我代码里有说明。代码如下：
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define _ ios::sync_with_stdio(false)
bool SUBMIT = 1;
typedef long long ll;
using namespace std;
const double PI = acos(-1);
const int inf = 2*1e5+100;
int n,cost[inf],ai[inf];//
int f[inf],check[inf];//f数组判断房间的情况是否考虑过。check数组确定当该房间
//考虑过后所需的最小花费。
int sor[inf];//用来判断房间成圈的情况
int dfs2(int a,int i,int source)
{
if(a==source){
sort(sor,sor+i);return sor[0];
}
sor[i]=cost[a];
return dfs2(ai[a],i+1,source);
}
int dfs(int a,int i,int &source)
{
f[a]=1;
if(ai[a]==a){//当老鼠进入某一个房间后就不出来的情况
check[a]=cost[a];
return cost[a];
}
if(f[ai[a]]&&check[ai[a]]){//当老鼠跑到一个已经考虑过情况的房间时，花费
//为0，因此，source置为1，表明该次花费不用记录在内。到时check数组还必须要更新
check[a]=check[ai[a]];source=1;
return check[ai[a]];
}
if(f[ai[a]]&&!check[ai[a]]){//当老鼠在一个房间圈内转圈时，要把这个圈的
//所有房间花费都排下序，然后取出最小的即可
int c=ai[a];
sor[0]=cost[c];
check[a]=dfs2(ai[c],1,c);
return check[a];
}
int ans=dfs(ai[a],i+1,source);
check[a]=ans;
return ans;
}
int main()
{
if(!SUBMIT)freopen("i.txt","r",stdin);else _;
cin>>n;memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)cin>>cost[i];
for(int i=1;i<=n;i++)cin>>ai[i];
int ans=0;
for(int i=1;i<=n;i++)
{
if(!f[i]){
int m=0,c=0;
c=dfs(i,0,m);//这里其实是我最初写的框架，但是最后有改动，第二个
//参数其实没有用
if(!m)ans+=c;
//cout<<i<<" "<<ans<<endl;
}
}
cout<<ans<<endl;
return 0;
}欢迎大家观看，如果有喜欢的可以关注一波O(∩_∩)O哈哈~