CodeForces 1027D 并查集做法最简单的做法没有之一

62 阅读 0 评论 41 点赞

我是靠谱客的博主霸气小猫咪，最近开发中收集的这篇文章主要介绍CodeForces 1027D 并查集做法最简单的做法没有之一，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://codeforces.com/problemset/problem/1027/D

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

Copy

5
1 2 3 2 10
1 3 4 3 3

output

Copy

input

Copy

4
1 10 2 10
2 4 2 2

output

Copy

input

Copy

7
1 1 1 1 1 1 1
2 2 2 3 6 7 6

output

Copy

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:

1→2→2→…1→2→2→…;
2→2→…2→2→…;
3→2→2→…3→2→2→…;
4→3→2→2→…4→3→2→2→…;
5→6→7→6→…5→6→7→6→…;
6→7→6→…6→7→6→…;
7→6→7→…7→6→7→…;

So it's enough to set traps in rooms 22 and 66.

题目大意：一只老鼠从任意房间出现，可以从一个房间到另外一个制定的房间，我们可以在房间放下陷阱，每个房间的陷进有指定的value，问最小的value和。

这题看好多人都用图论做的，可惜我是弱鸡，不会那玩意，于是首先想到的是并查集。

首先来梳理一下思路：

1.每个点的出度肯定为一

2.如果所有点构成一棵树，答案就是树根的value（假设 fa[b] = a 我们就说a是b的根）

3.如果是一个森林，答案就是多个树根的value之和

上面三点是显然易见的

但是如果有强连通分量呢假如 1->2->3->4 然后 4->1 这样就形成了一个强连通的分量，是一个环，显然我们肯定选环里面的最小值作为这个环的答案，另外如果这个环有尾巴的话，也可以一并考虑，比如上面不是 4->1而是4->2，1显然就是尾巴了，从1出发可以到环里面任一点，所以可以视为它在环内。然后就直接干咯。

这里我用的边带权的并查集，每个点维护从它到树根的一个最小值，当出现环的时候，把树根的权值替换成环中的最小值就行了

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 2e5+110;
int a[maxn],fa[maxn],b[maxn];
int get(int x){
   if(x == fa[x]) return x;
   int root = get(fa[x]);
   a[x] = min(a[x],a[fa[x]]);//利用递归维护最小值
   return fa[x] = root;
}
void merge(int x,int y){
   int v = get(y);//因为x的出度肯定为1，所以没必要get
   if(x!=v)
   fa[x] = v;//这里不要把x和v写反了，方向要确定
   a[x] = min(a[x],a[y]);//这里y不要写成v，因为v是已经路径压缩后的点了，直接指向了根，竟然x指向y，y维护了最小，就找a[y];这是易错点
}
int main(){
   scanf("%d",&n);
   for(int i = 1; i <= n; i++)
   scanf("%d",&a[i]),fa[i] = i;
   int pos;
   for(int i = 1; i <= n; i++){
       scanf("%d",&pos);
       merge(i,pos);
   }
   int ans = 0;
   for(int i = 1; i <= n; i++)
   if(fa[i] == i)ans+=a[i];//如果是树根就加上
   printf("%dn",ans);
   return 0;
}