抓捕盗窃犯

题目描述

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

输入描述:

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

题意描述：

求出设置关卡使得抓到的盗窃犯最多输出最多数量。

解题思路：

因已给出逃犯到达一个地点及下一地点的序号。利用并查集使得各个地点的序号联系起来，有关系的地点有一个共同的祖先。再将有联系的地点的逃犯数累加到祖先位置，再将得到的序列从大到小排序，前m个地点逃犯的和即为抓到的最大逃犯数。

官方题解：
把每个地点看作一个点，那么每个点一定有且仅有一条有向出边。
每个点出度只有1，如果某些点组成了一个有向环，这个环上所有点不会有额外的出边，即这个环一定是一个简单环。
也易证每个点最终都会走向一个环。
结论:单独看待每个联通块，每个连通块一定有且只有一个环，只要在这个环上任何一个点建立哨卡，就能抓到这个联通块中的所有。可以使用把边都看成无向，使用并查集等找出所有连通块并求每个连通块上所有点的数量之和，从大到小排序，取前m大即可。
复杂度O(nlogn)

程序代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int f[100010],a[100010],v[100010];
long long st[100010];
long long cmp(long long a,long long b)
{
	return a>b;
} 
	
int get_f(int i)
{
	if(f[i]==i)
		return i;
	else
	{
		f[i]=get_f(f[i]);
		return f[i];
	} 
}

void merge(int v,int u)
{
	int t1,t2;
	t1=get_f(v);
	t2=get_f(u);
	if(t1!=t2)
	{
		f[t2]=t1;
	}
}
int main()
{
	int n,m,i;
	long long ans;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			f[i]=i;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(i=1;i<=n;i++)
			scanf("%d",&v[i]);
		for(i=1;i<=n;i++)
		{
			merge(i,v[i]);//并查集将有关系的地点联系起来 
		}
		memset(st,0,sizeof(st));
		for(i=1;i<=n;i++)
			st[get_f(i)]+=a[i];//累加有关系地点的逃犯，加到祖先序号位置。 
		sort(st+1,st+n+1,cmp);
		ans=0;
		for(i=1;i<=m;i++)
			ans+=st[i];
		printf("%lld\n",ans);
	}
	return 0;
}