cf Educational Codeforces Round 49 D. Mouse Hunt

原题：
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⋅10^5) — the number of rooms in the dormitory.

The second line contains n integers c1,c2,…,cn (1≤ci≤10^4) — 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
input
5
1 2 3 2 10
1 3 4 3 3
output
3
input
4
1 10 2 10
2 4 2 2
output
10
input
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
output
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.

中文：

有一个楼里有一只老鼠，这只老鼠在第0秒的时候可以在任意一个屋子当中，这只老鼠为位置i会在下一秒的时候移动到位置ai，如果ai==i表示这只老鼠没动。一共有n个屋子，在这n个不同的屋子放置一个捕鼠夹的价格ci。现在问你设计一个策略，使用最少的价钱放置捕鼠夹，是的这只老鼠被抓到。

#include<bits/stdc++.h>
using namespace std;
const int maxn=200001;
int V;

vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> vs;
bool used[maxn];
int cmp[maxn];
int Next[maxn];
int c[maxn];
int father[maxn];

void add_edge(int from,int to)
{
	G[from].push_back(to);
	rG[to].push_back(from);
}
void dfs(int v)
{
	used[v]=true;
	for(int i=0;i<G[v].size();i++)
	{
		if(!used[G[v][i]])
			dfs(G[v][i]);
	}
	vs.push_back(v);
}
void rdfs(int v,int k)
{
	used[v]=true;
	cmp[v]=k;
	for(int i=0;i<rG[v].size();i++)
	{
		if(!used[rG[v][i]])
			rdfs(rG[v][i],k);
	}
}
int scc()
{
	memset(used,0,sizeof(used));
	vs.clear();
	for(int v=1;v<=V;v++)
		if(!used[v])
			dfs(v);

	memset(used,0,sizeof(used));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--)
		if(!used[vs[i]])
			rdfs(vs[i],k++);

	return k;
}


void ini()
{
	for(int i=0;i<=V;i++)
	{
		father[i]=INT_MAX;
		G[i].clear();
		rG[i].clear();
	}
}




int main()
{
	ios::sync_with_stdio(false);
	while(cin>>V)
	{
		ini();
		for(int i=1;i<=V;i++)
			cin>>c[i];
		for(int i=1;i<=V;i++)
		{
			cin>>Next[i];
			add_edge(i,Next[i]);
		}
		int k=scc();
		for(int i=1;i<=V;i++)//构造缩点图
		{
            if(father[cmp[i]]==INT_MAX)
                father[cmp[i]]=i;
            else
            {
                if(c[i]<c[father[cmp[i]]])
                    father[cmp[i]]=i;
            }
		}
		int ans=0;
		memset(used,false,sizeof(used));
		for(int i=1;i<=V;i++)
        {
            if(father[cmp[i]]==father[cmp[Next[i]]]&&!used[father[cmp[i]]])
            {
                ans+=c[father[cmp[i]]];
                used[father[cmp[i]]]=true;
            }
        }
        cout<<ans<<endl;
	}
	return 0;
}

解答：

把在第i位置老鼠要到ai位置的这个关系构造成一个有向图，那么可以知道，一定要放置捕鼠夹的位置一定是当前这个图中最后所有节点都流向的那个节点，或者是一个连通分量。

那么可以用这样的思路，先构造图中的连通分量，然后构建缩点，缩点当中保留鼠夹价格最小。在对缩点后的图计算拓扑排序，实际上构造缩点后的图，只要有一个节点指向自己或者该节点不指向任何节点，则该点就是要放置鼠夹的地方。

此题和poj那个popular cow挺像的