「银河队营养师」题解

问题分析

我们有 $n$ 种营养和两套厨师机器人，每套有 $n$ 个机器人。每个机器人做的菜可以提供特定的营养组合。我们需要为第一套的每个机器人匹配第二套的一个机器人作为备份，使得当任意一个第一套机器人坏掉时，用其备份替换后，整个系统仍然能够组合出任何营养需求。

核心思路

这个问题可以转化为二分图匹配问题，并使用高斯消元和最小费用流来解决。

1. 数学模型

设：

• 第一套机器人矩阵为 $A$（$n \times n$）
• 第二套机器人矩阵为 $B$（$n \times n$）

当第一套的第 $i$ 个机器人用第二套的第 $j$ 个机器人备份时，需要满足：用 $B_j$ 替换 $A_i$ 后，新的矩阵仍然满秩（即可逆）。

2. 算法步骤

步骤1：计算第一套机器人的逆矩阵

f(i, 1, n) {
    if (fabs(a.a[i][i]) < eps) {
        // 寻找可交换的行
        f(j, i, n) if (fabs(a.a[j][i]) > eps) {
            f(k, 1, 2*n) swap(a.a[i][k], a.a[j][k]);
            break;
        }
    }
    // 高斯消元...
}

通过高斯-约当消元法计算 $A^{-1}$，如果 $A$ 不可逆则直接输出 NIE。

步骤2：计算有效备份关系

计算 $C = B \times A^{-1}$，如果 $C_{ij} \neq 0$，则第二套的第 $j$ 个机器人可以作为第一套第 $i$ 个机器人的备份。

f(i, 1, n) f(j, 1, n) f(k, 1, n)
    c.a[i][j] += b.a[i][k] * a.a[k][j];

步骤3：构建二分图并求匹配

• 左部：第一套的 $n$ 个机器人
• 右部：第二套的 $n$ 个机器人
• 边：当 $C_{ij} \neq 0$ 时，从第一套的第 $i$ 个机器人到第二套的第 $j$ 个机器人连边

f(i, 1, n) f(j, 1, n) if (fabs(c.a[i][j]) > eps)
    ad(j, i + n, 1, 0), mp[j][i] = cnt;

步骤4：求字典序最小的完美匹配

使用最小费用流算法，并通过特殊技巧保证字典序最小：

f(i, 1, n) {
    S = i;
    bfs();
    // 尝试用更小编号的备份替换当前匹配
    f(j, 1, ma[i]-1) if (mp[i][j] && dis[j+n] != inf) {
        // 调整匹配关系
        ma[i] = j;
        break;
    }
}

关键算法细节

1. 高斯消元求逆矩阵

• 将 $A$ 和单位矩阵拼接成 $[A|I]$
• 通过行变换将 $A$ 变为单位矩阵，此时右边的 $I$ 就变成了 $A^{-1}$

2. 网络流建模

• 源点 $S$ 连向所有第一套机器人，容量1，费用0
• 所有第二套机器人连向汇点 $T$，容量1，费用0
• 有效的备份关系连边，容量1，费用0

3. 字典序优化

在找到任意完美匹配后，按顺序为每个第一套机器人尝试匹配更小编号的第二套机器人，如果存在调整路径则进行调整。

复杂度分析

• 高斯消元：$O(n^3)$
• 矩阵乘法：$O(n^3)$
• 网络流：$O(n^3)$（SPFA算法）
• 总复杂度：$O(n^3)$，对于 $n \leq 300$ 可接受

样例验证

样例1

第一套：单位矩阵
第二套：对角矩阵

显然每个机器人只能匹配相同编号的备份，输出 1 2 3。

样例2

通过计算逆矩阵和矩阵乘法，找到字典序最小的匹配 3 4 1 2。

总结

本题综合运用了：

1. 线性代数：矩阵求逆、矩阵乘法
2. 图论：二分图匹配
3. 网络流：最小费用最大流
4. 贪心：字典序优化

通过将营养搭配问题转化为矩阵的可逆性问题，再转化为图匹配问题，最终用网络流算法高效解决。