题解 [CEOI2005] Depot Rearrangement

hellhell · 2021-11-11 21:19:14 · 题解

[CEOI2005] Depot Rearrangement

题目描述

一家公司经营着 n 个店铺，每个店铺都销售 m 种不同的产品。该公司有一个大型仓库，产品在运送到商店之前在都会那里进行包装。每家商店将会收到相同数量的每种产品。因此，该公司将一定数量的相应产品分别包装到一个集装箱中，并用产品标识符标记该集装箱。产品由 1 到 m 的数字标识。

因此，在包装结束后，仓库中将会有 n\cdot m 个集装箱，并且正好 n 个集装箱贴有每种产品的对应标签。由于该仓库位于一个狭窄的建筑物内，所以集装箱排成了一排。但为了加快配送速度，仓库经理想要重新排列集装箱。由于将产品配送到商店是通过向每个商店发出一辆卡车来实现的，并且每辆卡车运载每种产品的一个集装箱，其合适的安排如下。该行最前部分 m 个集装箱必须贴有不同的产品标签，该行的第二部分 m 个集装箱必须贴有不同的产品标签，依此类推。

不幸的是，在这一行的尽头只有一个空闲的地方可以放置一个集装箱。因此，必须通过依次拿起集装箱并将其移动到空闲位置来进行重新排列。重新排列后，空闲位置也必须在行的末尾。目标是通过最少的移动以实现所需的重新排列。

计算需要最少移动多少次使得达成目标重排，输出最少的移动次数和具体的操作方案，每一步操作是形如 (x,y) 的二元组，表示将 x 位置上的集装箱移动到位置 y 上。

样例输入：

5  6
4 1 3 1 6 5 2 3 2 3 5 6 2 1 4 5 6 4 1 3 2 4 5 5 1 2 3 4 6 6

样例输出：

思路分析

不难发现，对于每一部分的集装箱，同种类只出现过一次的集装箱我们是不会动它的，我们会移动的是同种类出现次数大于 1 的集装箱。

设 t_{i,j} 表示 [(i-1)\cdot m+1,i\cdot m] 区间内，种类为 j 的集装箱出现的次数。

考虑构造二分图，左边点集为 \{p_1,p_2,p_3\cdots,p_n\} 表示第 i 段长度为 m 的区间，右边点集为 \{ q_1,q_2,q_3,\cdots q_m\} 表示集装箱的种类。

若 t_{i,j}>1 ，则在图中从 p_i 向 q_j 连接 t_{i,j}-1 条有向边。

若 t_{i,j}=0，则在图中从 q_j 向 p_i 连接一条有向边。

对样例建立二分图

通过这样的方法构造出的二分图，其中一条从左到右再到左的路径为 p_i\to q_j \to p_k，表示将 p_i 中种类为 q_j 的集装箱放到 p_k 的空位中。每次被放入集装箱的一段区间，一定要保证存在一个空位，为了保证操作次数最小，我们要尽可能地让 n\cdot m+1 变成空地的次数最小。

每当我们在图中走完一条回路时，n\cdot m+1 会为空，所以我们需要让找到的回路条数尽可能地少。也就是对于图中的每一个极大联通子图求一遍欧拉回路。然后按照欧拉回路构造方案即可。

可以证明图中每个子图一定存在欧拉回路。因为我们建边是根据 t_{i,j} 来建边的，最终对集装箱安排好位置后，每一部分一定都有每种集装箱各 1 个，所以初始状态，每多一个相同的种类的集装箱，就会少一种不同种类的集装箱。也就是每连接一条 p_i\to q_j 的边同时也会伴随着连接一条 q_k\to p_i 的边。有向图中，每一个点的入度与出度都相等，则一定存在欧拉回路。

具体的构造方案为，对于每一个极大联通子图任选一个点当起点，求欧拉回路。

记录经过的边的编号序列，倒序遍历序列，每遇到 p_i\to q_j 的边就把 q_j 移到空地上，同时更新空地的位置。

为什么要倒序枚举序列？每次的移动相当于在图中经过 p_i\to q_j\to p_k，每次移动都要保证 q_j 想移动到的位置 p_k 是空的，那么倒序枚举就可以保证 p_k 一定是空的了，因为我们在移动 p_i 中的集装箱时，上一步一定是移动了 p_k 中的集装箱。第一次移动集装箱，将集装箱移动到 n\cdot m+1 上。最后再将 n\cdot m+1 位置上的集装箱移动到现在的空地即可。

对于一个具有 E 条边的极大联通子图，所需的操作次数为 \frac{E}{2}+1。

空间只有 64MB，实现时，记录每个集装箱位置的数组，要用 vector 来存。

代码实现

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read() {
    int f = 1;
    int res = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * f;
}

const int maxn = 410;

int n, m;
vector < int > pos[maxn][maxn];//用 vector 实现，不然会 MLE
int tot[maxn][maxn];

struct node {
    int from;
    int to;
    int next;
}
edge[maxn * maxn * 2];
int head[maxn << 1];
int cnt;

void add(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].from = u;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int que[maxn * maxn * 2], tag;
bool vis[maxn * maxn * 2];

void dfs(int now) {
    for (int i = head[now]; i; i = edge[i].next) {
        if (vis[i])
            continue;
        int v = edge[i].to;
        vis[i] = true;
        dfs(v);
        que[++tag] = i;
    }
}

struct ANS {
    int x;
    int y;
}
ans[maxn * maxn + maxn];
int len;

signed main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x = read();
            ++tot[i][x];
            pos[i][x].push_back((i - 1) * m + j);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k < tot[i][j]; k++) {
                add(i, j + n);
            }
            if (tot[i][j] < 1)
                add(j + n, i);
        }
    }
    for (int i = n + 1; i <= n + m; i++) {
        tag = 0;
        dfs(i);
        int to = n * m + 1;
        for (int i = 1; i <= tag; i++) {
            int u = edge[que[i]].from;
            int v = edge[que[i]].to;
            if (u <= n) {
                ans[++len].x = pos[u][v - n][--tot[u][v - n]];
                ans[len].y = to;
                to = ans[len].x;
            }
        }
        if (tag) {
            ans[++len].x = n * m + 1;
            ans[len].y = to;
        }
    }
    printf("%lld\n", len);
    for (int i = 1; i <= len; i++) {
        printf("%lld %lld\n", ans[i].x, ans[i].y);
    }
    return 0;
}