BZOJ 1119 - [POI2009]SLO

#数学 #贪心 #置换
Published on 2016-09-21

题目地址

描述

对于一个 的排列 (ai)(a_i)，每次你可以交换两个数 axa_x 与 ，代价为 W(ax)+W(ay)W(a_x)+W(a_y)，若干次交换的代价为每次交换的代价之和。请问将 (ai)(a_i) 变为 (bi)(b_i) 所需的最小代价是多少。

分析

我们将 (ai),(bi)(a_i), (b_i) 乘上 (ai)(a_i) 这个置换的逆，这样就使得 (ai)(a_i) 变为 。
(bi)(b_i) 也就成为了一个置换了，我们就是要通过交换，来实现这个置换，根据常用方法，将 (bi)(b_i) 分解为循环。对于循环 ii，设长度为 sis_i，可以发现至少要进行 si−1s_i - 1 次交换才能达到目标，不妨用代价最小的元素与其余 si−1s_i - 1 个元素各交换一次，这样代价为 sumi+mni(si−1)\mathrm{sum}_i + \mathrm{mn}_i(s_i - 1)，sumi\mathrm{sum}_i 为这个循环中的代价和，mni\mathrm{mn}_i 为这个循环中的最小值。

对每个循环独立处理，是不是就能得到最优解了呢？并不一定，我们可以将 ii 中的最小元素 mni\mathrm{mn}_i 先与全局的最小元素 mn\mathrm{mn} 调换，然后用 mn\mathrm{mn} 进行 si−1s_i - 1 次交换，接着换回 mni\mathrm{mn}_i 与 mn\mathrm{mn}，这样的代价为 sumi+mni+mn(si+1)\mathrm{sum}_i + \mathrm{mn}_i + \mathrm{mn}(s_i + 1)。
于是每个循环都可以选择是否换进最小值（不用担心能不能成立，我们只需要安排含有最小值的循环最后操作即可），答案为：

∑i=1ssumi+min(sumi+mni(si−1),sumi+mni+mn(si+1))\sum_{i = 1}^s\mathrm{sum}_i + \min\left(\mathrm{sum}_i + \mathrm{mn}_i(s_i - 1), \mathrm{sum}_i + \mathrm{mn}_i + \mathrm{mn}(s_i + 1)\right)

代码

//  Created by Sengxian on 09/20/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1119 置换 + 贪心
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000000 + 3;
int n, _w[MAX_N], w[MAX_N], a[MAX_N], b[MAX_N], mark[MAX_N];
bool vis[MAX_N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    ll ans = 0;
    int m = INT_MAX;

    for (int i = 0; i < n; ++i) ans += _w[i] = ReadInt(), m = min(m, _w[i]);
    for (int i = 0; i < n; ++i) a[i] = i, mark[ReadInt() - 1] = i;
    for (int i = 0; i < n; ++i) w[mark[i]] = _w[i];
    for (int i = 0; i < n; ++i) b[i] = mark[ReadInt() - 1];

    for (int i = 0; i < n; ++i) if (!vis[i]) {
        int u = i, sz = 0, _mn = INT_MAX;
        do {
            vis[u] = true;
            sz++, _mn = min(_mn, w[u]);
            u = b[u];
        } while (!vis[u]);
        ans += min((ll)(sz - 2) * _mn, _mn + (ll)(sz + 1) * m);
    }

    printf("%lld\n", ans);
    return 0;
}
BZOJ 2525 - [Poi2011]Dynamite