题目链接
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 imes n) 的矩阵 (A)。那么，整套机器人能搭配出任何营养需求等价于将矩阵 (A) 化为行阶梯形矩阵后拥有 (n) 个非零行，即该矩阵为满秩矩阵。
由于满秩矩阵即可逆矩阵，矩阵 (A) 可逆等价于矩阵 (A) 的行列式值 (|A| eq 0)，因此，我们的任务是快速求出矩阵 (A) 在替换了某一行的元素后的行列式的值。不难想到通过行列式按行展开法则来计算行列式的值，即假如替换的是矩阵 (A) 的第 (i) 行，那么有（以下用 (A_{i, j}) 表示矩阵的 ((i, j)) 元的代数余子式，矩阵的行列标号为 (1 sim n)）：
其中的 (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
", answer[i] + 1);
}
}
return 0;
}