题目理解

我们需要设计一个 $4$ 输入、$4$ 输出的逻辑电路，要求：

• 只允许使用 $2$ 输入、$1$ 输出的门电路
• 可用门电路种类和数量有限制
• 使用最少数目的门电路
• 必须满足给定的 $16$ 种输入组合下的输出真值表

---

核心思路

1. 问题建模

将电路设计问题转化为状态空间搜索问题：

• 状态：当前已构建的电路（门电路及其连接关系）
• 初始状态：只有 $4$ 个输入端子（编号 $1$-$4$）
• 目标状态：电路能实现要求的 $4$ 个输出功能

2. 布尔函数表示

每个信号线（包括输入、输出和中间门输出）的布尔函数用一个 $16$ 位整数表示：

$$g[i] = \sum_{j=0}^{15} (f(j) \ll j)$$

其中 $f(j)$ 表示在第 $j$ 种输入组合下的输出值（$0$ 或 $1$）。

---

算法解析

1. 数据结构

int n, m;                    // n:总节点数, m:元件种类数
int t[N] = {0};              // t[i]:节点i使用的元件类型
int f[N][2][2] = {{{0}}};    // f[type][x][y]:元件真值表

bool vis[N] = {false};       // vis[i]:节点i是否已使用
int g[N] = {0};              // g[i]:节点i的布尔函数
int fa[N][2] = {{0}};        // fa[i][0/1]:节点i的两个输入

int h[N] = {0};              // h[1..4]:四个输出的目标函数
int ans = 0;                 // 最少需要的门电路数

2. 预处理计算

// 预计算所有可能的门电路输出
void calc(int tp, int x, int y) {
    cc[tp][x][y] = 0;
    for (int i = 0; i < 8; i++)
        cc[tp][x][y] += (1 << i) * f[tp][x >> i & 1][y >> i & 1];
}

对于每种元件类型，预计算所有输入组合下的输出，加速后续搜索。

3. 深度优先搜索

核心搜索函数 dfs(k, used, lt, d)：

• k：当前已使用的门电路数量
• used：已满足的输出位掩码（$1$<<$(i-1)$ 表示第 $i$ 个输出已满足）
• lt：上次使用的元件类型（用于剪枝）
• d：当前搜索深度

搜索过程：

1. 如果所有 $4$ 个输出都满足（used == 15），找到解
2. 剪枝：如果当前解不可能优于已知最优解，提前返回
3. 枚举所有已存在的节点对 $(x, y)$ 作为新门的输入
4. 枚举所有可用的元件类型
5. 计算新门的输出函数，检查是否能满足新的输出
6. 递归搜索

4. 剪枝策略

if (k + 1 >= ans || k + popcnt[used ^ 15] >= ans)
    return;

• 最优性剪枝：当前解已不优于已知最优解
• 必要性剪枝：至少还需要 $\text{popcnt}(used \oplus 15)$ 个门才能满足所有输出

5. 输出电路

找到解后，通过拓扑排序确定门电路的连接顺序：

// 拓扑排序确定输出顺序
queue<int> q;
for (int i = 5; i <= n; i++)
    if (resf[i] && ind[i] == 0)
        q.push(i);

while (!q.empty()) {
    int x = q.front(); q.pop();
    if (x <= 4) continue;
    id[x] = idx--;
    if (--ind[res[x][0]] == 0) q.push(res[x][0]);
    if (--ind[res[x][1]] == 0) q.push(res[x][1]);
}

---

关键算法技术

1. 状态压缩

• 用 $16$ 位整数表示 $16$ 种输入组合下的输出
• 用位运算高效计算门电路输出

2. 迭代加深搜索

for (int i = 0; i <= n - 4; i++) {
    ans = i + 1;
    dfs(0, used, 1, 1);
    if (ans != i + 1) break;
}

从最少门电路数开始尝试，逐步增加限制。

3. 对称性剪枝

pii t2 = mp(min(x, y), max(x, y));
if (pmn < t2) { ... }

避免重复计算输入顺序不同的相同电路。

4. 记忆化搜索

if (!VIS[ng]) 
    VIS[ng] = true, dfs(...), VIS[ng] = false;

避免重复搜索产生相同布尔函数的电路结构。

---

复杂度分析

• 状态空间：$O(2^{16} \times n^2)$（布尔函数数量 × 节点对数量）
• 搜索深度：最多 $10$ 层（元件总数限制）
• 实际效率：通过强力剪枝，在数据范围内可解

---

算法总结

这是一个典型的组合搜索问题，通过：

1. 布尔函数压缩表示提高效率
2. 迭代加深框架保证找到最优解
3. 多重剪枝策略减少搜索空间
4. 拓扑排序输出确保连接顺序正确