一看问题就像置换一样。……找到循环节，然后假设循环节的长度是l，如果只在循环中交换，每个数字必须至少计入一次成本，总共有2*(l-1)答案中包含了个数，显然除了每个数至少剩下一次l-最小的答案是最好的两次
然而，这可能不是这个循环中最好的。我们可以强行拉一个不在循环中的数字，所以我们必须让所有数字中最小的和循环中最小的交换，拉所有数字中最小的，然后让所有数字中最小的都包含在答案中l-两次，然后在这个数字和循环节中更换最小的
对每个循环节把这两种方法取min，加入答案
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 1000010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long int n; int a[MAXN],b[MAXN],w[MAXN]; int p[MAXN]; bool vis[MAXN]; ll ans; int MN=INF; int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i ){ scanf("%d",&w[i]); MN=min(MN,w[i]); } for(i=1;i<=n;i ){ scanf("%d",&a[i]); p[a[i]]=i; } for(i=1;i<=n;i ){ scanf("%d",&b[i]); } for(i=1;i<=n;i ){ if(!vis[i]&&a[i]!vis[i]&&a[i]!=b[i]){ int x=i; int mn=INF; int siz=0; ll sum=0; while(!vis[x]){ vis[x]=1; sum =w[a[x]]; siz ; if(w[a[x]]<=mn){ mn=w[a[x]]; } x=p[b[x]]; } ans =min(sum (ll)mn*(siz-2),sum mn (ll)MN*(siz 1)); } } printf("%lld\n",ans); return 0; } /* */