出题人题解 | #抓捕***犯#

原题解链接：https://ac.nowcoder.com/discuss/157310

把每个地点看作一个点，那么每个点一定有且仅有一条有向出边。

每个点出度只有$11$，如果某些点组成了一个有向环，这个环上所有点不会有额外的出边，即这个环一定是一个简单环。

也易证每个点最终都会走向一个环。

结论:单独看待每个联通块，每个连通块一定有且只有一个环，只要在这个环上任何一个点建立哨卡，就能抓到这个联通块中的所有。可以使用把边都看成无向，使用并查集等找出所有连通块并求每个连通块上所有点的数量之和，从大到小排序，取前$mm$大即可。

复杂度$O(nlogn)O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int a[100005];

bool vis[100005];
ll sum;
ll tmp;
vector<ll> ans;
vector<int> g[100005];
void dfs(int u){
    vis[u]=1;
    tmp+=a[u];
    for(auto v:g[u])if(!vis[v])dfs(v);
}

int main(){
    int cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        if(a[i]<=0) printf("haha");
    }
    for(int i=1;i<=n;i++){
    	int v;
        scanf("%d",&v);
        if(v>n||v<=0) printf("haha");
        g[i].push_back(v);
        g[v].push_back(i);
        cnt++;
    }
    if(cnt!=n) cout<<"wowo";
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            tmp=0;
            dfs(i);
            ans.push_back(tmp);
        }
    }
    sort(ans.begin(),ans.end());
    for(int i=ans.size()-1; i>=0;i--){
        if(m)m--,sum+=ans[i];
    }
    cout<<sum;
    return 0;
}