比赛 |
2025.9.6 |
评测结果 |
MEETTTTTTMMMMMMMMTMMT |
题目名称 |
Bessie s Function |
最终得分 |
0 |
用户昵称 |
秋_Water |
运行时间 |
38.777 s |
代码语言 |
C++ |
内存使用 |
303.42 MiB |
提交时间 |
2025-09-06 11:20:24 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
vector<int>G[N];
int a[N],w[N],n,m,fa[N],vis[N],f[N][2],bk;
void add(int u,int v){
G[u].push_back(v);
fa[v]=u;
}
int check(int u){
vis[u]=1;
int ff=fa[u];
if(vis[ff]){
return ff;
}
else{
check(ff);
}
}
void dfs(int u){
f[u][0]=0;
f[u][1]=w[u];
vis[u]=1;
for(auto v:G[u]){
if(v!=bk){
dfs(v);
f[u][1]+=f[v][0];
f[u][0]+=min(f[v][0],f[v][1]);
}
}
}
int calc(int u){
int tmp=0;
bk=check(u);
dfs(bk);
tmp=f[bk][0];
bk=fa[bk];
dfs(bk);
tmp=min(tmp,f[bk][0]);
return tmp;
}
int main(){
freopen("Function.in","r",stdin);
freopen("Function.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>w[i];
if(a[i]==i){
w[i]=0;
}
}
for(int i=1;i<=n;i++){
add(a[i],i);
}
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
ans+=calc(i);
}
}
cout<<ans;
return 0;
}