比赛 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;
}