并查集 牛客练习赛41 C抓捕盗窃犯

时间:2021-07-05 00:46:33

题目链接 :https://ac.nowcoder.com/acm/contest/373/C

题意,初始每一个城市都有一伙盗贼,没过一个时刻盗贼就会逃窜到另一个城市,你可以在m个城市设置监察站,会逮捕所有经过该城市的盗贼

分析:仔细分细题目,因为每个城市的盗贼都是流动的,这就可能会形成环,而如果成环的话,在环所在任一城市都可以把这批城市的全部盗贼逮捕,就不需要再环上设多个监察站了,进一步推广,因为可以自己往自己的城市跑,所以也有可能是链,而链也是满足设一个监察站可以逮捕所有

自然想到引入并查集,用map来保存

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int mod=1e9+;
ll a[maxn],v[maxn];
ll par[maxn];
ll rnk[maxn];
ll c[maxn];
bool cmp(const ll &a,const ll &b){
return a>b;
}
void init(){
for(ll i=;i<maxn;i++) par[i]=i,rnk[i]=;
}
ll find(ll x){
if(par[x]==x){
return x;
}
else{
return par[x]=find(par[x]);
}
}
void unite(ll x,ll y){
x=find(x);y=find(y);
if(x==y) return ;
if(rnk[x]<rnk[y]){
par[x]=y;
}else {
par[y]=x;
if(rnk[x]==rnk[y]) rnk[x]++;
}
}
bool same(ll x,ll y){
return find(x)==find(y);
}
int main(){
ll n,m;scanf("%lld%lld",&n,&m);
init();
for(int i=;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=;i<=n;i++){
scanf("%lld",&v[i]);
unite(i,v[i]);
}
map<ll,ll> ans;
map<ll,ll>::iterator ite;
for(ll i=;i<=n;i++){
ans[find(i)]+=a[i];
}
//for(int i=1;i<=n;i++) cout<<find(i)<<" ";
int j=;
for(ite=ans.begin();ite!=ans.end();++ite){
c[j++]=ite->second;
}
sort(c,c+ans.size(),cmp);
ll cnt=;
for(ll i=;i<m&&i<ans.size();i++){
cnt+=c[i];}//cout<<c[i]<<endl;}
cout<<cnt<<endl;
return ;
}