##题目链接
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)$。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 3e2 + 10, mod = 1e9 + 7;
void add(int& x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
int mul(int x, int y) {
return (long long) x * y % mod;
}
int qpow(int v, int p) {
int result = 1;
for (; p; p >>= 1, v = mul(v, v)) {
if (p & 1) {
result = mul(result, v);
}
}
return result;
}
int n, a[N][N], b[N][N], inv[N][N], adj[N][N], choice[N], visit[N], tt, answer[N];
vector<int> go[N];
void transform1(int a[N][N], int i, int j) {
for (int p = 0; p < n; ++p) {
swap(a[i][p], a[j][p]);
}
}
void transform2(int a[N][N], int i, int k) {
for (int p = 0; p < n; ++p) {
a[i][p] = mul(a[i][p], k);
}
}
void transform3(int a[N][N], int i, int j, int k) {
for (int p = 0; p < n; ++p) {
add(a[i][p], mul(a[j][p], k));
}
}
void get_adj() {
int det = 1;
for (int i = 0; i < n; ++i) {
inv[i][i] = 1;
}
for (int i = 0; i < n; ++i) {
if (!a[i][i]) {
int p = i;
for (int j = i + 1; j < n; ++j) {
if (a[j][i]) {
p = j;
}
}
if (p == i) {
puts("NIE");
exit(0);
}
transform1(a, i, p);
transform1(inv, i, p);
det = (mod - det) % mod;
}
det = mul(det, a[i][i]);
int x = qpow(a[i][i], mod - 2);
transform2(a, i, x);
transform2(inv, i, x);
for (int j = i + 1; j < n; ++j) {
int p = a[j][i];
transform3(a, j, i, (mod - p) % mod);
transform3(inv, j, i, (mod - p) % mod);
}
}
for (int i = n - 1; ~i; --i) {
for (int j = i + 1; j < n; ++j) {
int p = a[i][j];
transform3(a, i, j, (mod - p) % mod);
transform3(inv, i, j, (mod - p) % mod);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
adj[i][j] = mul(inv[j][i], det);
}
}
}
bool find(int u) {
for (int i = 0; i < go[u].size(); ++i) {
int v = go[u][i];
if (visit[v] != tt) {
visit[v] = tt;
if (!~choice[v] || find(choice[v])) {
choice[v] = u;
return true;
}
}
}
return false;
}
bool find_better(int u, int down) {
for (int i = 0; i < go[u].size(); ++i) {
int v = go[u][i];
if (visit[v] != tt) {
visit[v] = tt;
if (choice[v] == down || (choice[v] > down && find_better(choice[v], down))) {
answer[u] = v;
choice[v] = u;
return true;
}
}
}
return false;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &a[i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &b[i][j]);
}
}
get_adj();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int det = 0;
for (int k = 0; k < n; ++k) {
add(det, mul(b[j][k], adj[i][k]));
}
if (det) {
go[i].push_back(j);
}
}
}
memset(choice, -1, sizeof choice);
int total = 0;
for (int i = 0; i < n; ++i) {
++tt;
total += find(i);
}
if (total != n) {
puts("NIE");
} else {
puts("TAK");
for (int i = 0; i < n; ++i) {
++tt;
find_better(i, i);
printf("%d\n", answer[i] + 1);
}
}
return 0;
}