題干：

鏈接：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

解題報告：

注意到每個點的入度雖然不唯一，但是每個點的出度一定為1.也就是說只要這個圖是聯通的，那么一定能都匯集到同一個點上。所以我們只需要看看有多少個連通圖就可以，這個過程可以用dfs來實現，也可以用并查集?。最后貪心出答案來。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; ll n,m; ll num[MAX]; int nt[MAX]; ll val[MAX]; int tot; bool vis[MAX]; ll tmp; vector<int> vv[MAX]; void dfs(int cur,int root) {vis[cur] = 1;tmp += num[cur];int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(vis[v] == 0) dfs(v,cur);} } int main() {cin>>n>>m;for(int i = 1; i<=n; i++) scanf("%lld",num+i);for(int i = 1; i<=n; i++) {scanf("%d",nt+i);vv[i].pb(nt[i]);vv[nt[i]].pb(i);}for(int i = 1; i<=n; i++) {if(!vis[i]) {tmp = 0;dfs(i,-1);val[++tot] = tmp;}}sort(val+1,val+tot+1);ll ans = 0;for(int i = tot; i>max(0LL,tot-m); i--) {ans += val[i];}printf("%lld\n",ans);return 0 ;}

1WA了，，，最下面tot寫成了 tmp、、

總結

以上是生活随笔為你收集整理的【牛客 - 373C】抓捕盗窃犯（连通图，思维，dfs 或 并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。