链接：https://ac.nowcoder.com/acm/contest/373/C
来源：牛客网
 

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

作者：lililalala
链接：https://ac.nowcoder.com/discuss/157310
来源：牛客网

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

牛客网参考代码：

#include<bits/stdc++.h>
using namespace std;
vector<long long> v;
int pre[100010];
int val[100010];
long long msc[100010];
int find(int x)
{
    int r=x;
    while(pre[r] != r)
          r=pre[r];
    int i=x,j;
    while(i!=r)
    {
         j = pre[i];
         pre[i]= r ;
         i=j;
    }
    return r;
}
void join(int x,int y)                                                                                                                                                                                        //如果已经连通，就不用管了 //如果不连通，就把它们所在的连通分支合并起
{
    int fx=find(x),fy=find(y);
    if(fx!=fy) pre[fx]=fy;
}
void solve(){
    long long ans=0;
    int n,m;
    scanf("%d %d",&n,&m);
    v.clear();
    memset(msc,0,sizeof(msc));
    for(int i=1;i<=n;i++) pre[i]=i;
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        join(i,x);
    }
    for(int i=1;i<=n;i++) msc[find(i)]+=val[i];
    for(int i=1;i<=n;i++) if(msc[i]) v.push_back(msc[i]);
    sort(v.begin(),v.end(),greater<long long>());
    for(int i=0;i<min((long long)m,(long long)v.size());i++) ans+=v[i];
    printf("%lld\n",ans);
}
int main()
{
    solve();
    return 0;
}

笔者参考代码：

#include<iostream>
#include<algorithm>
#define ll long long int
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
struct node
{
    ll x,y;
} a[N];
ll pre[N],n,m,ans[N];
ll find(ll n)
{
    return n == pre[n]?n:pre[n] = find(pre[n]);
}
void Join(ll a,ll b)
{
    a=find(a);
    b=find(b);
    if(a != b)
    {
        pre[a] = b;
    }
}
void init()
{
    for(ll i=1; i<=n; i++)
        pre[i] = i;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    init();
    for(ll i=1; i<=n; ++i)
        cin>>a[i].x;
    for(ll i=1; i<=n; ++i)
    {
        cin>>a[i].y;
        Join(i,a[i].y);
    }
    for(ll i=1; i<=n; ++i)
        ans[find(i)]+=a[i].x;
    sort(ans+1,ans+100001,greater<ll>());
    ll sum=0;
    for(ll i=1; i<=m; i++)
        sum+=ans[i];
    cout<<sum<<endl;
    return 0;
}