Description：

对于一个 $1\sim N$ 的排列 $a_i$ ，每次你可以交换两个数 $a_x$ 与 $a_y(x\ne y)$ ，代价为 $W(a_x)+W(a_y) $ 若干次交换的代价为每次交换的代价之和。请问将 $a_i$ 变为 $b_i$ 所需的最小代价是多少。

$1\leqslant n\leqslant 10^6$

Solution：

把每个向他在另一个序列的位置连边，每个点入度为一出度为一一定是很多环，如果环大小为 $1$ ，那就不用管，如果大小为 $2$ ，直接交换，如果大小 $\geqslant 3$ ，那就有两种方式，一是拿一个环中的最小的一个一个换下去，二是从外面拿一个最小的充当媒介，分别计算一下代价取 $\min$ 累加即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int w[MAXN];

int a[MAXN],b[MAXN];

int fr[MAXN];

struct edge

{

	int to,nxt,w;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int w)

{

	e[++edgenum] = (edge){b,lin[a],w};lin[a] = edgenum;

	return;

}

bool v[MAXN];

int tot = 0;

vector<int> c[MAXN];

void get(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		c[tot].push_back(e[i].w);

		if(!v[e[i].to])get(e[i].to);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&w[i]);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)scanf("%d",&b[i]);

	for(int i = 1;i <= n;++i)fr[a[i]] = i;

	for(int i = 1;i <= n;++i)add(fr[b[i]],i,w[a[i]]);

	for(int i = 1;i <= n;++i)

	{

		if(!v[i])

		{

			++tot;

			get(i);

		}

	}

	int minn = 0x3f3f3f3f;

	for(int i = 1;i <= n;++i)minn = min(minn,w[i]);

	long long ans = 0;

	for(int i = 1;i <= tot;++i)

	{

		if(c[i].size() == 1)continue;

		if(c[i].size() == 2)

		{

			ans += c[i][0] + c[i][1];

			continue;

		}

		long long val1 = 0,val2 = 0;

		int minv = 0x3f3f3f3f;

		for(int j = 0;j < c[i].size();++j)

		{

			minv = min(minv,c[i][j]);

			val1 += c[i][j];

		}

		val1 += (long long)minv * (c[i].size() - 2);

		for(int j = 0;j < c[i].size();++j)

		{

			val2 += c[i][j];

		}

		val2 += minv + (long long)minn * (c[i].size() + 1);

		ans += min(val1,val2);

	}

	cout << ans << endl;

	return 0;

}