1 条题解
-
0
拓扑排序找环,再统计环上最小值,贡献给 。
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e5+10; int n,x[N],rd[N];ll c[N]; bool vis[N];queue<int>q; void ts() { for(int i=1;i<=n;i++) if(rd[i]==0)q.push(i); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=1;int v=x[u];rd[v]--; if(rd[v]==0)q.push(v); } } ll calc(int u) { ll res=c[u]; while(!vis[u]) { res=min(res,c[u]); vis[u]=1;u=x[u]; } return res; } void work() { ll ans=0; for(int i=1;i<=n;i++) if(!vis[i])ans+=calc(i); printf("%lld\n",ans); } signed main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x[i]),rd[x[i]]++; for(int i=1;i<=n;i++)scanf("%lld",&c[i]); ts();work();return 0; }
- 1
信息
- ID
- 9979
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 3
- 上传者