Educational Codeforces Round 49 (Rated for Div. 2) 1027D Mouse Hunt(基环树找环)
D. Mouse Hunt
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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
3
input
Copy
4 1 10 2 10 2 4 2 2
output
Copy
10
input
Copy
7 1 1 1 1 1 1 1 2 2 2 3 6 7 6
output
Copy
2
题意:
有一只老鼠，会随机把1-n中的一个房间作为起点。现在你已经知道了老鼠的运动规矩，a[i]表示，当老鼠到达i房间，下一步一定是到a[i]房间。现在你要放置捕鼠器，每一个房间放置捕鼠器的花费是c[i]，问你最少的花费使你一定能捕到老鼠
解析:
这个就是一个基环树，每一个点出度为1
基环树，也是环套树，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。因此，对基环树的处理大部分就是对树处理和对环处理。
因为起点随机，所以我们只需要在根放置捕鼠器就可以了，但是根可能会与某些点形成环，这样这些与根形成环的点就互相等价了，相当于一个点。那么在这些点里面我们只需要找c[i]最小的点放置捕鼠器就可以了。
并且基环树形成环的一定是根的位置形成环的(因为每一个点出度为1)，那么找环就可以直接用并查集来做
一旦两个点x,y形成x->y这条边之前已经在一个并查集里面了，那么一定是成环了，并且x一定是根节点
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define Min(a,b) a>=b?b:a
using namespace std;
typedef long long ll;
const int MAXN =2e5+2;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n;
ll c[MAXN];
int ufset[MAXN];
ll vis[MAXN];
int pre[MAXN];
int find(int x)
{
if(x==ufset[x])
{
return x;
}
int nex=ufset[x];
ufset[x]=find(nex);
return ufset[x];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&c[i]);
ufset[i]=i;
vis[i]=c[i];
}
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
pre[i]=tmp;
int fx=find(i);
int fy=find(tmp);
if(fx!=fy)
{
ufset[fx]=fy;
}
else
{
ll minn=vis[fx];
int kk=tmp;
while(kk!=fx)
{
minn=Min(minn,vis[kk]);
kk=pre[kk];
}
vis[fx]=minn;
}
}
for(int i=1;i<=n;i++) find(i);
ll ans=0;
for(int i=1;i<=n;i++)
{
if(ufset[i]==i)
{
ans+=vis[i];
}
}
printf("%lld\n",ans);
}