T12:Cube

题解：三维立方体选数最小和（x、y、z 都不能重复）

题目概述

给你一个 n×n×n 的立方体，每个位置 (x,y,z) 有一个权值。你要选出 n 个位置，使得：

• 任何两个被选位置的 x 不相同
• 任何两个被选位置的 y 不相同
• 任何两个被选位置的 z 不相同

在满足以上限制的前提下，让权值总和最小。

n <= 12。

---

核心思路：按 x 分层 + 状态压缩 DP

因为每个 x 只能用一次，我们可以按 x=1..n 依次决定“这一层选哪个 (y,z)”。

当已经处理了前 k 个 x 时，我们已经选了 k 个点，也就用掉了：

• k 个不同的 y
• k 个不同的 z

所以用两个二进制集合表示使用情况：

• ymask：哪些 y 已经用过
• zmask：哪些 z 已经用过

并且必须满足：ymask 中 1 的个数等于 zmask 中 1 的个数（因为每选一个点就同时消耗一个 y 和一个 z）。

---

状态定义

把所有 mask 按 popcount（1 的个数）分层。

在第 k 层（表示已用 k 个 y、k 个 z，等价于已经处理完 x=1..k）：

• cur[iy][iz] 表示：

  ymask = lst[k][iy]，zmask = lst[k][iz] 时的最小总和。

其中 lst[k] 是所有 popcount(mask)=k 的 mask 列表。

---

初始化

k=0 时只有一种状态：

• ymask=0，zmask=0，代价为 0

即：cur[0][0]=0

---

转移

从第 k 层转到第 k+1 层，此时要处理的 x 是：

• x = k + 1

对当前状态 (ymask, zmask)：

1. 枚举一个没用过的 y
2. 枚举一个没用过的 z
3. 选择点 (x, y, z)，进入新状态：
   • ymask2 = ymask | (1<<(y-1))
   • zmask2 = zmask | (1<<(z-1))
   • 新代价 = 旧代价 + cost[x][y][z]

取最小值更新到下一层 nxt。

为了能快速从 mask 找到它在 lst[k+1] 里的位置，用 pos[mask] 做映射（O(1) 找下标）。

---

结果

当 k=n 时，ymask 和 zmask 都必须是全 1（全部用过）：

• 输出对应状态的最小值即可。

---

复杂度

• 状态只枚举同层的有效 mask，规模大约是 C(n,k)^2。
• 每个状态转移枚举剩余的 y、z，数量最多是 (n-k)^2。
• n <= 12 时整体运算量在可接受范围内，且内存远小于直接开 dp[4096][4096]，不会 MLE，也比哈希版常数小很多，通常也不会 TLE。

---

参考代码

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

const long long INF = (1LL << 62);
const int MAXN = 12;
const int MAXM = 1 << MAXN;

// cost[x][y][z]，下标从 1 开始
static int cost[13][13][13];

// lst[k] 存 popcount = k 的所有 mask
static int lst[13][MAXM];
static int cnt[13];

// pos[mask]：mask 在下一层 lst[k+1] 里的下标
static int pos[MAXM];

// 每层最多 C(12,6)=924，这里开 1000 足够
static long long cur[1000][1000];
static long long nxt[1000][1000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 读入：共 n*n 行，每行 n 个数
    // 顺序：先 x，再 y，每个 (x,y) 读一行 z=1..n
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            for (int z = 1; z <= n; z++) {
                cin >> cost[x][y][z];
            }
        }
    }

    int FULL = (1 << n) - 1;

    // 预处理按 popcount 分组的 mask 列表
    for (int mask = 0; mask <= FULL; mask++) {
        int k = __builtin_popcount((unsigned)mask);
        lst[k][cnt[k]++] = mask;
    }

    // k=0 层：只有 (0,0)
    cur[0][0] = 0;

    // 从 k=0 推到 k=n
    for (int k = 0; k < n; k++) {
        int x = k + 1;

        int CY = cnt[k], CZ = cnt[k];
        int NY = cnt[k + 1], NZ = cnt[k + 1];

        // 建 pos：mask -> 在 lst[k+1] 里的下标
        for (int i = 0; i <= FULL; i++) pos[i] = -1;
        for (int i = 0; i < NY; i++) pos[lst[k + 1][i]] = i;

        // 初始化 nxt
        for (int i = 0; i < NY; i++) {
            for (int j = 0; j < NZ; j++) {
                nxt[i][j] = INF;
            }
        }

        // 枚举当前层有效状态
        for (int iy = 0; iy < CY; iy++) {
            int ymask = lst[k][iy];
            for (int iz = 0; iz < CZ; iz++) {
                long long base = cur[iy][iz];
                if (base >= INF) continue;

                int zmask = lst[k][iz];

                // 选一个没用过的 y
                for (int y = 1; y <= n; y++) {
                    int ybit = 1 << (y - 1);
                    if (ymask & ybit) continue;

                    int y2 = ymask | ybit;
                    int iy2 = pos[y2];

                    // 选一个没用过的 z
                    for (int z = 1; z <= n; z++) {
                        int zbit = 1 << (z - 1);
                        if (zmask & zbit) continue;

                        int z2 = zmask | zbit;
                        int iz2 = pos[z2];

                        long long v = base + cost[x][y][z];
                        if (v < nxt[iy2][iz2]) nxt[iy2][iz2] = v;
                    }
                }
            }
        }

        // 下一层覆盖到当前层
        for (int i = 0; i < NY; i++) {
            for (int j = 0; j < NZ; j++) {
                cur[i][j] = nxt[i][j];
            }
        }
    }

    // 找 FULL 在 lst[n] 里的下标
    int idxFull = -1;
    for (int i = 0; i < cnt[n]; i++) {
        if (lst[n][i] == FULL) { idxFull = i; break; }
    }

    cout << cur[idxFull][idxFull] << endl;
    return 0;
}