抓捕盗窃犯（并查集）

 

题目描述

Q市发生了一起特大盗窃案。这起盗窃案是由多名盗窃犯联合实施的,你要做的就是尽可能多的抓捕盗窃犯。
已知盗窃犯分布于 N N个地点,以及第 i i个地点初始有 ai ai名盗窃犯。
特别的是，对于每一个地点 u u,都有一个固定的地点 v v--当前如果某个盗窃犯位于地点 u u,在下一个时刻他会移动到地点 v v。
你需要通过初始时在某些点设置哨卡来捉住他们。
现在你可以在 M M个地点设置哨卡,如果在某个地点设置哨卡,你可以抓获在任一时刻经过该地点的盗窃犯。
也就是说,哨卡存在的时间是无限长,但哨卡不能移动。

输入描述:

第一行两个整数 N,M(1≤N,M≤105) N,M(1≤N,M≤105)。
第二行 N N个整数 a1a2...aN a1a2...aN (0≤a1,a2,...aN≤105) (0≤a1,a2,...aN≤105),表示第 i i个地点初始有 ai ai名盗窃犯。
第三行 N N个整数 v1v2...vN v1v2...vN (1≤v1,v2,...vN≤N) (1≤v1,v2,...vN≤N),表示当前处于地点 i i的盗窃犯下一个时刻会移动到地点 vi vi。

输出描述:

输出一行一个整数--能够抓捕到的最大数量。

示例1

输入

复制

8 2
1 2 3 4 1 2 3 12
2 3 3 3 6 7 5 8

输出

复制

22

说明

对于样例一，一种可行的方案是：

在地点3、地点8分别设置一个哨卡，此时答案为1+2+3+4+12=22

示例2

输入

复制

8 2
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 8

输出

复制

36

说明

对于样例二，一种可行的方案是：

在地点2、地点8分别设置一个哨卡，此时答案为1+2+3+4+5+6+7+8=36

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

typedef long long ll;
using namespace std;
int  a[100005];
ll pre[100005];
ll b[100005];
ll find(ll x)
{
   if(pre[x]==x)
   {
   	return x;
	}	
    else
    {
    	return pre[x]=find(pre[x]);
	}
}
void merge(int x,int y)
{
	ll fx=find(x);
	ll fy=find(y);
	if(fx!=fy)
	{
		pre[fx]=fy;
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int t=1;t<=n;t++)
	{
		scanf("%d",&a[t]);
	}
	for(int t=1;t<=n;t++)
	{
     pre[t]=t;
	}
	int x;
	for(int t=1;t<=n;t++)
	{
		scanf("%d",&x);
		merge(x,t);
	}
	for(int t=1;t<=n;t++)
	{
		b[find(t)]+=a[t];
	}
	sort(b+1,b+n+1);
	ll s=0;
	for(int t=n;t>=n-m+1;t--)
	{
		s+=b[t];
	}
	cout<<s<<endl;
	
	return 0;
}