BZOJ1119：置换群的轮换计数

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define INF 0x7f7f7f7f
 4 using namespace std;
 5 const int maxn=1000005;
 6 int n,cnt,vmin;
 7 bool vis[maxn];
 8 int a[maxn],w[maxn],pos[maxn],to[maxn];
 9 int mn[maxn],size[maxn];
10 long long ans;
11 long long sum[maxn];
12 int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f-=1; ch=getchar();}
16     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
17     return x*f;
18 }
19 void solve()
20 {
21     for(int i=1;i<=n;i++) vmin=min(vmin,w[i]);
22     for(int i=1;i<=n;i++)
23     if(!vis[i])
24     {
25         cnt++;mn[cnt]=w[a[i]];
26         int k=i;
27         while(1)
28         {
29             vis[k]=1;
30             mn[cnt]=min(mn[cnt],w[a[k]]);
31             sum[cnt]+=w[a[k]];
32             size[cnt]++;
33             k=to[k];
34             if(k==i) break;
35         }
36     }
37     for(int i=1;i<=cnt;i++)
38     {
39         long long t1=(long long)(size[i]-2)*mn[i]+sum[i];
40         long long t2=(long long)(size[i]+1)*vmin+sum[i]+mn[i];
41         ans+=min(t1,t2);
42     }
43 }
44 void init()
45 {
46     vmin=INF;
47     
48 }
49 int main()
50 {
51     init();
52     n=read();
53     for(int i=1;i<=n;i++) w[i]=read();
54     for(int i=1;i<=n;i++) a[i]=read();
55     for(int i=1;i<=n;i++) {int x=read();pos[x]=i;}
56     for(int i=1;i<=n;i++) to[i]=pos[a[i]];
57     solve();
58     printf("%lld",ans);
59     return 0;
60 }