1 条题解

  • 0
    @ 2026-4-8 21:21:56

    拓扑排序找环,再统计环上最小值,贡献给 ansans

    #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
    上传者