题目理解

我们有一个 $n \times n \times n$ 的三维立方体，需要选择 $n$ 个数，满足：

• 任意两个选择的数不能有相同的 $x$ 坐标
• 任意两个选择的数不能有相同的 $y$ 坐标
• 任意两个选择的数不能有相同的 $z$ 坐标

这意味着选择的 $n$ 个数恰好占据 $n$ 个不同的 $x$、$n$ 个不同的 $y$、$n$ 个不同的 $z$。换句话说，我们是在寻找一个 三维匹配：选择 $n$ 个位置 $(x,y,z)$，使得每个 $x$ 恰好出现一次、每个 $y$ 恰好出现一次、每个 $z$ 恰好出现一次。

这等价于在一个 $n \times n$ 的矩阵中，每个格子对应一个 $n$ 维向量（$z$ 维），我们需要从每个 $x$ 和 $y$ 的组合中选一个 $z$，并且 $z$ 不能重复。

问题转化

设 $a[x][y][z]$ 表示立方体中位置 $(x,y,z)$ 的值。

我们需要选择 $n$ 个位置 $(x_i, y_i, z_i)$ 使得：

• $\{x_1, ..., x_n\} = \{1,2,...,n\}$
• $\{y_1, ..., y_n\} = \{1,2,...,n\}$
• $\{z_1, ..., z_n\} = \{1,2,...,n\}$

最小化 $\sum_{i=1}^n a[x_i][y_i][z_i]$。

这是一个三维分配问题（3-dimensional assignment problem），是 NP-hard 问题。但由于 $n \le 12$，我们可以使用状态压缩动态规划来解决。

算法思路

由于 $n \le 12$，我们可以枚举 $x$ 的排列。固定 $x$ 的顺序后，问题转化为：对于每个 $x$，我们需要分配一个 $(y,z)$ 对，使得所有 $y$ 和所有 $z$ 都恰好使用一次。

更具体地说：

1. 按 $x$ 从 $1$ 到 $n$ 依次考虑
2. 维护两个布尔数组（或位掩码）表示哪些 $y$ 和哪些 $z$ 已经被使用
3. 对于当前的 $x$，我们可以选择任意未被使用的 $y$ 和 $z$，加上对应的值 $a[x][y][z]$
4. 使用 DP：$dp[mask_y][mask_z]$ 表示已经处理完前 $k$ 个 $x$（其中 $k$ 等于 $mask_y$ 或 $mask_z$ 中 1 的个数），且已使用的 $y$ 集合为 $mask_y$，已使用的 $z$ 集合为 $mask_z$ 时的最小和

由于 $n \le 12$，$mask_y$ 和 $mask_z$ 各有 $2^n = 4096$ 种状态，总状态数为 $4096 \times 4096 \approx 16.7 \times 10^6$，对于每个状态我们可能需要遍历 $O(n^2)$ 种选择，总复杂度约为 $16.7 \times 10^6 \times 144 \approx 2.4 \times 10^9$，在 C++ 中优化后可能勉强通过。

优化

我们可以进一步优化：

注：$k = \text{popcount}(mask_y) = \text{popcount}(mask_z)$，因为我们已经处理了 $k$ 个 $x$，所以 $mask_y$ 和 $mask_z$ 必须有相同数量的 1。这可以减少状态数。

更常见的做法是只用一个 $mask_y$，然后对于每个 $x$，我们枚举所有未使用的 $y$（通过 $mask_y$），但 $z$ 的分配需要另外处理。实际上，我们可以将问题看作：选择 $n$ 个 $(y,z)$ 对，每个 $y$ 和 $z$ 恰好出现一次，且每个 $x$ 对应一个不同的 $(y,z)$ 对。

我们可以预先计算 $cost[x][y][z]$，然后使用匈牙利算法的变种？不行，这是三维问题。

更好的 DP 状态定义：

• 令 $dp[mask_y][mask_z]$ 表示已经考虑了前 $k = \text{popcount}(mask_y) = \text{popcount}(mask_z)$ 个 $x$ 时的最小和
• 转移时，我们考虑第 $k+1$ 个 $x$（即 $x = k+1$），枚举所有 $y$ 不在 $mask_y$ 中、$z$ 不在 $mask_z$ 中的组合，进行转移

复杂度：状态数 $3^n$？不，仍然是 $2^{2n}$，但每个状态转移需要 $O(n^2)$，总复杂度 $O(2^{2n} \cdot n^2)$，当 $n=12$ 时，$2^{24} \cdot 144 \approx 2.4 \times 10^9$，需要优化。

进一步优化

我们可以采用最小费用最大流的思路，或者使用DP + 预处理：

对于固定的 $mask_y$ 和 $mask_z$，$k = \text{popcount}(mask_y)$ 是确定的。我们可以预处理所有可能的 $(mask_y, mask_z)$ 对，只考虑 $\text{popcount}(mask_y) = \text{popcount}(mask_z)$ 的状态，状态数约为 $\sum_{k=0}^n \binom{n}{k}^2$，当 $n=12$ 时，这个和约为 $2.7 \times 10^6$（根据中心二项式系数近似）。

转移时，我们不需要枚举所有 $O(n^2)$ 种 $(y,z)$ 对，可以枚举所有不在 $mask_y$ 中的 $y$，然后对于每个这样的 $y$，枚举所有不在 $mask_z$ 中的 $z$。但这样仍然是 $O(n^2)$。

我们还可以使用位运算枚举子集的技巧，但这里枚举的是补集，无法直接优化。

实现方案

由于 $n=12$ 时状态数约为 $2.7 \times 10^6$，每个状态转移约 $O(144)$，总运算量约 $3.9 \times 10^8$，在 C++ 中经过优化（使用数组、位运算、预编译）可以 3 秒内通过。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9;
int n;
int a[13][13][13];
int dp[1 << 12][1 << 12];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    
    // 读入数据
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                cin >> a[i][j][k];
            }
        }
    }
    
    // 初始化 DP 数组
    int full_mask = (1 << n) - 1;
    for (int i = 0; i <= full_mask; i++) {
        for (int j = 0; j <= full_mask; j++) {
            dp[i][j] = INF;
        }
    }
    
    dp[0][0] = 0;
    
    // DP 转移
    for (int mask_y = 0; mask_y <= full_mask; mask_y++) {
        int x = __builtin_popcount(mask_y);  // 当前处理的 x 编号（0-based 或 1-based）
        // 注意：我们的 x 从 1 到 n，但这里 x 表示已经处理了 x 个层（即 x 从 0 到 n-1）
        if (x >= n) continue;
        
        for (int mask_z = 0; mask_z <= full_mask; mask_z++) {
            if (__builtin_popcount(mask_z) != x) continue;
            if (dp[mask_y][mask_z] == INF) continue;
            
            int cur = dp[mask_y][mask_z];
            int remaining_y = full_mask ^ mask_y;
            int remaining_z = full_mask ^ mask_z;
            
            // 枚举所有未使用的 y 和 z
            // 为了优化，我们可以枚举 y，然后枚举 z
            for (int y = 0; y < n; y++) {
                if (!(remaining_y >> y & 1)) continue;
                for (int z = 0; z < n; z++) {
                    if (!(remaining_z >> z & 1)) continue;
                    int new_mask_y = mask_y | (1 << y);
                    int new_mask_z = mask_z | (1 << z);
                    int new_val = cur + a[x + 1][y + 1][z + 1];
                    if (new_val < dp[new_mask_y][new_mask_z]) {
                        dp[new_mask_y][new_mask_z] = new_val;
                    }
                }
            }
        }
    }
    
    cout << dp[full_mask][full_mask] << "\n";
    
    return 0;
}

时间复杂度分析

• 状态数：约 $\sum_{k=0}^n \binom{n}{k}^2 \approx \binom{2n}{n} \approx 2.7 \times 10^6$（当 $n=12$ 时）
• 每个状态转移：$O(n^2) = 144$
• 总运算量：约 $3.9 \times 10^8$ 次操作，在 C++ 优化下可在 3 秒内完成

空间复杂度

$O(2^{2n}) = O(4096 \times 4096 \times 4 \text{ bytes}) \approx 64 \text{ MB}$，在限制内。