本文共 3618 字，大约阅读时间需要 12 分钟。
Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80%80% of applicants are girls and majority of them are going to live in the university dormitory for the next 44 (hopefully) years.
The dormitory consists of nn 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 ii costs cici burles. Rooms are numbered from 11 to nn .
Mouse doesn't sit in place all the time, it constantly runs. If it is in room ii in second tt then it will run to room aiai in second t+1t+1 without visiting any other rooms inbetween (i=aii=ai means that mouse won't leave room ii ). It's second 00 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 11 to nn at second 00 .
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 nn (1≤n≤2⋅1051≤n≤2⋅105 ) — the number of rooms in the dormitory.
The second line contains nn integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤1041≤ci≤104 ) — cici is the cost of setting the trap in room number ii .
The third line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n ) — aiai is the room the mouse will run to the next second after being in room ii .
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
Input
51 2 3 2 101 3 4 3 3
Output
3
Input
41 10 2 102 4 2 2
Output
10
Input
71 1 1 1 1 1 12 2 2 3 6 7 6
Output
2
Note
In the first example it is enough to set mouse trap in rooms 11 and 44 . If mouse starts in room 11 then it gets caught immideately. If mouse starts in any other room then it eventually comes to room 44 .
In the second example it is enough to set mouse trap in room 22 . If mouse starts in room 22 then it gets caught immideately. If mouse starts in any other room then it runs to room 22 in second 11 .
Here are the paths of the mouse from different starts from the third example:
So it's enough to set traps in rooms 22 and 66 .
题意：
有n个房间，n条边， 有一只老鼠， 随机从n个房间出现，求需要花费多少老鼠夹才能确定老鼠一定会被抓住。 。
此题困扰了我好久，感觉无从下手。 。。 然后看题解，都说是找环， 为啥是找环。 。。
仔细想了想，n条边，n个顶点，而且每个顶点只能有一个出度。 。。 那么说肯定有环的出现。 。因为以上最后一条边无论加在哪里都会构成连通。 。。
然后此题确实是找环。 。。 找到组成环的点集中花费最小的点， 然后只要其他点经过环中的任意一点， 就不需要多余的花费了。 。。
说起来容易， 可是写起来难啊。 。。 半天写出个程序还是错的。 。。 看了别人的代码， 才略懂。 。。
代码如下：
#include#include #include #include using namespace std;const int maxn=2e5+5;const int INF=0x3f3f3f3f;int n;int c[maxn];int vis[maxn]; //代表dfs时的起点int sum=0;int a[maxn];int dfs (int x,int s){ if(vis[x]) //如果有起点，则直接退出 return INF; vis[x]=s; int next=a[x]; int Min=INF; if(vis[next]==s) //如果下一条边为起点，表明成环了，下面进行找最小值操作 { Min=min(c[x],Min); int u=a[x]; while (u!=x) { Min=min(c[u],Min); u=a[u]; } return Min; } return dfs(a[x],s);}int main(){ memset (vis,0,sizeof(vis)); 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]); for (int i=1;i<=n;i++) { int temp=dfs(i,i); if(temp
转载地址：http://wtaen.baihongyu.com/