题解 P3482 【[POI2009]SLO-Elephants】

· · 题解

将数组 a,b 间下标相等或值相等的两个数连在一起：

发现可以组成三个“环”：(1,2,5),(3,4),(6)

这些环互不影响，可以逐个击破。

对于长度为 L 的环，注意到可以通过恰好 L-1 次交换使得环内每个数都归位。为了使总代价最小，我们先找出环内代价最小的数，然后依次将它与本应在它位置上的数交换，如此交换 L-1 次便可使环内所有数归位。

按照上述策略还原一个环的代价是：\text{sum}+\min_1\times(L-2)

但是，如果环内每个数代价都很大，就需考虑另一种策略：先找出**所有数**中代价最小的数，先将它与环内代价最小的数交换（相当于在环外搬救兵，找全局最小代替环内最小）。经 $L-1$ 次交换将环内的数复原后，再将全局最小与环内最小替换回来。 按照这种策略，还原一个环的代价是：$\text{sum}+\min_1+\min_2\times(L+1)

这里的 \min_2 是全局最小代价。

对于每个环无非就是上述两种策略，取代价小者加起来即可。

#include<bits/stdc++.h>
#define int long long
#define nb 1000010
using namespace std;

int n, ans, min2 = 2e9, a[nb], b[nb], A[nb], w[nb];
bool vis[nb];

void work(int x){
    int len = 0, sum = 0, min1 = 2e9;
    while(!vis[x]){
        vis[x] = 1;                 // 标记当前环内的数
        sum += w[a[x]];             // 累加当前环代价和
        min1 = min(min1, w[a[x]]);  // 找出环内最小代价
        x = A[b[x]];                // 跳至环内下一个数
        len++;                      // 统计当前环的长度
    }
    int p = sum + min1 * (len - 2); // 策略一
    int q = sum + min1 + min2 * (len + 1); // 策略二
    ans += min(p, q);
}

signed main(){
    cin >> n;
    ios::sync_with_stdio(0);
    for(int i = 1; i <= n; i++) cin >> w[i], min2 = min(min2, w[i]);
    for(int i = 1; i <= n; i++) cin >> a[i], A[a[i]] = i;   // 将值映射到 a 的下标
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) if(!vis[i]) work(i);        // 找到新环，逐个击破
    cout << ans;
    return 0;
}

最后顺便提一提，对于数组内交换的题，拆分成环考虑是常见的套路。可以顺便看看这两题：

P1667 数列

P4778 Counting swaps