##题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=3168
题解
首先，我们需要求出对于任意的 $i, j(1 \leq i, j \leq n)$，第二套中的第 $j$ 个机器人是否可以替换第一套中的第 $i$ 个机器人。
将第 $i$ 个机器人提供的第 $j$ 种营养的量记为 $a_{i, j}$，我们可以得到一个 $n \times n$ 的矩阵 $A$。那么，整套机器人能搭配出任何营养需求等价于将矩阵 $A$ 化为行阶梯形矩阵后拥有 $n$ 个非零行，即该矩阵为满秩矩阵。
由于满秩矩阵即可逆矩阵，矩阵 $A$ 可逆等价于矩阵 $A$ 的行列式值 $|A| \neq 0$，因此，我们的任务是快速求出矩阵 $A$ 在替换了某一行的元素后的行列式的值。不难想到通过行列式按行展开法则来计算行列式的值，即假如替换的是矩阵 $A$ 的第 $i$ 行，那么有（以下用 $A_{i, j}$ 表示矩阵的 $(i, j)$ 元的代数余子式，矩阵的行列标号为 $1 \sim n$）：
$$|A| = \sum_\limits{k = 1}^{n} a_{i, k}A_{i, k}$$
其中的 $a_{i, k}(1 \leq k \leq n)$ 为第 $i$ 行替换后的元素值。由于代数余子式 $A_{i, k}$ 的值与第 $i$ 行本身的元素无关，因此我们可以先用 $O(n^3)$ 的时间求出矩阵 $A$ 的伴随矩阵，从而得到矩阵所有元素对应的代数余子式的值。具体地，设矩阵 $A$ 的伴随矩阵为 $A^$，根据 $A^{-1} = \frac{1}{|A|}A^$ 可得 $A^* = |A|A^{-1}$，由于可以在 $O(n^3)$ 的时间内求出矩阵 $A$ 的逆矩阵 $A^{-1}$（并顺便求出矩阵 $A$ 的行列式值 $|A|$），因此自然能够在相同的时间内求出伴随矩阵。得到所有元素的代数余子式的值后，我们便能在 $O(n)$ 的时间内求出单次行替换后矩阵的行列式值。一共需要进行 $O(n^2)$ 次替换与判断，故预处理出每个机器人对应的替换集合所需的总时间复杂度为 $O(n^3)$。
预处理完毕后，我们就可以通过求二分图匹配来寻找解的方案。不过，注意到题目要求求出字典序最小的匹配，因此直接通过一次二分图匹配得到的方案并不是我们所需要的答案，我们需要在此基础上再进行一次贪心。具体地，我们从小到大枚举编号 $i$，然后判断在第一套机器人中编号小于 $i$ 的机器人的匹配状态不变的情况下，编号为 $i$ 的机器人能否与编号更优的机器人匹配即可。
总时间复杂度为 $O(n^3)$。
代码
1#include<bits/stdc++.h> 2 3using namespace std; 4 5const int N = 3e2 + 10, mod = 1e9 + 7; 6 7void add(int& x, int y) { 8 x += y; 9 if (x >= mod) { 10 x -= mod; 11 } 12} 13 14int mul(int x, int y) { 15 return (long long) x * y % mod; 16} 17 18int qpow(int v, int p) { 19 int result = 1; 20 for (; p; p >>= 1, v = mul(v, v)) { 21 if (p & 1) { 22 result = mul(result, v); 23 } 24 } 25 return result; 26} 27 28int n, a[N][N], b[N][N], inv[N][N], adj[N][N], choice[N], visit[N], tt, answer[N]; 29vector<int> go[N]; 30 31void transform1(int a[N][N], int i, int j) { 32 for (int p = 0; p < n; ++p) { 33 swap(a[i][p], a[j][p]); 34 } 35} 36 37void transform2(int a[N][N], int i, int k) { 38 for (int p = 0; p < n; ++p) { 39 a[i][p] = mul(a[i][p], k); 40 } 41} 42 43void transform3(int a[N][N], int i, int j, int k) { 44 for (int p = 0; p < n; ++p) { 45 add(a[i][p], mul(a[j][p], k)); 46 } 47} 48 49void get_adj() { 50 int det = 1; 51 for (int i = 0; i < n; ++i) { 52 inv[i][i] = 1; 53 } 54 for (int i = 0; i < n; ++i) { 55 if (!a[i][i]) { 56 int p = i; 57 for (int j = i + 1; j < n; ++j) { 58 if (a[j][i]) { 59 p = j; 60 } 61 } 62 if (p == i) { 63 puts("NIE"); 64 exit(0); 65 } 66 transform1(a, i, p); 67 transform1(inv, i, p); 68 det = (mod - det) % mod; 69 } 70 det = mul(det, a[i][i]); 71 int x = qpow(a[i][i], mod - 2); 72 transform2(a, i, x); 73 transform2(inv, i, x); 74 for (int j = i + 1; j < n; ++j) { 75 int p = a[j][i]; 76 transform3(a, j, i, (mod - p) % mod); 77 transform3(inv, j, i, (mod - p) % mod); 78 } 79 } 80 for (int i = n - 1; ~i; --i) { 81 for (int j = i + 1; j < n; ++j) { 82 int p = a[i][j]; 83 transform3(a, i, j, (mod - p) % mod); 84 transform3(inv, i, j, (mod - p) % mod); 85 } 86 } 87 for (int i = 0; i < n; ++i) { 88 for (int j = 0; j < n; ++j) { 89 adj[i][j] = mul(inv[j][i], det); 90 } 91 } 92} 93 94bool find(int u) { 95 for (int i = 0; i < go[u].size(); ++i) { 96 int v = go[u][i]; 97 if (visit[v] != tt) { 98 visit[v] = tt; 99 if (!~choice[v] || find(choice[v])) { 100 choice[v] = u; 101 return true; 102 } 103 } 104 } 105 return false; 106} 107 108bool find_better(int u, int down) { 109 for (int i = 0; i < go[u].size(); ++i) { 110 int v = go[u][i]; 111 if (visit[v] != tt) { 112 visit[v] = tt; 113 if (choice[v] == down || (choice[v] > down && find_better(choice[v], down))) { 114 answer[u] = v; 115 choice[v] = u; 116 return true; 117 } 118 } 119 } 120 return false; 121} 122 123int main() { 124 scanf("%d", &n); 125 for (int i = 0; i < n; ++i) { 126 for (int j = 0; j < n; ++j) { 127 scanf("%d", &a[i][j]); 128 } 129 } 130 for (int i = 0; i < n; ++i) { 131 for (int j = 0; j < n; ++j) { 132 scanf("%d", &b[i][j]); 133 } 134 } 135 get_adj(); 136 for (int i = 0; i < n; ++i) { 137 for (int j = 0; j < n; ++j) { 138 int det = 0; 139 for (int k = 0; k < n; ++k) { 140 add(det, mul(b[j][k], adj[i][k])); 141 } 142 if (det) { 143 go[i].push_back(j); 144 } 145 } 146 } 147 memset(choice, -1, sizeof choice); 148 int total = 0; 149 for (int i = 0; i < n; ++i) { 150 ++tt; 151 total += find(i); 152 } 153 if (total != n) { 154 puts("NIE"); 155 } else { 156 puts("TAK"); 157 for (int i = 0; i < n; ++i) { 158 ++tt; 159 find_better(i, i); 160 printf("%d\n", answer[i] + 1); 161 } 162 } 163 return 0; 164}