题意可转化为：给定 \(2n\) 个行向量，分别为 \(A_{1\dots n}\) 和 \(B_{1\dots n}\)，求一个字典序最小的 \(1\dots n\) 的排列 \(P\)，满足 \(A_{1\dots i-1},B_{P_i},A_{i+1\dots n}\) 线性不相关。
设 \(V_{i,j}\) 表示用 \(A_{1\dots n}\) 线性组合出 \(B_i\) 时 \(A_j\) 的系数。
那么有 \(B_{i,j} = \sum\limits_{k=1}^n V_{i,k} A_{k,j}\)，即 \(B = VA\)，即 \(V = BA^{-1}\)。
那么矩阵求逆求出 \(V\) 之后，若 \(V_{i,j} \ne 0\)，则连接 \(B_i,A_j\)。这是因为若不满足此条件，意味着用除 \(A_j\) 之外的行向量可以表示出 \(B_i\)，交换后便不满足线性无关；否则易得其仍然线性无关。
如何求字典序最小的二分图完美匹配？
首先任意求出一组匹配，然后枚举 \(1 \dots n\)，分别贪心地强制选取目前最小的匹配点，并查看是否还可匹配成功。
需要使用匈牙利算法实现，复杂度 \(O(n^3)\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
using namespace std;
const int N = 300;
const double eps = 1e-6;
int n;
int e[N + 5][N + 5];
double a[N + 5][N + 5],b[N + 5][N + 5],inv[N + 5][N + 5],v[N + 5][N + 5];
int vis[N + 5],match[N + 5],ans[N + 5];
int dfs(int p)
{
for(register int i = 1;i <= n;++i)
if(e[p][i] && !vis[i])
{
vis[i] = 1;
if(!match[i] || dfs(match[i]))
{
match[i] = p;
return 1;
}
}
return 0;
}
int dfs(int p,int rt)
{
for(register int i = 1;i <= n;++i)
if(e[p][i] && !vis[i])
{
vis[i] = 1;
if(match[i] == rt || (match[i] > rt && dfs(match[i],rt)))
{
match[i] = p;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
inv[i][i] = 1;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= n;++j)
scanf("%lf",a[i] + j);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= n;++j)
scanf("%lf",b[i] + j);
for(register int i = 1;i <= n;++i)
{
if(fabs(a[i][i]) <= eps)
for(register int j = i + 1;j <= n;++j)
if(fabs(a[j][i]) > eps)
{
for(register int k = 1;k <= n;++k)
swap(a[i][k],a[j][k]),swap(inv[i][k],inv[j][k]);
break;
}
if(fabs(a[i][i]) <= eps)
{
puts("NIE");
return 0;
}
double x = a[i][i];
for(register int j = 1;j <= n;++j)
a[i][j] /= x,inv[i][j] /= x;
for(register int j = i + 1;j <= n;++j)
{
x = a[j][i];
for(register int k = 1;k <= n;++k)
a[j][k] -= a[i][k] * x,inv[j][k] -= inv[i][k] * x;
}
}
for(register int i = n - 1;i;--i)
for(register int j = i + 1;j <= n;++j)
{
double x = a[i][j];
for(register int k = 1;k <= n;++k)
a[i][k] -= a[j][k] * x,inv[i][k] -= inv[j][k] * x;
}
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= n;++j)
for(register int k = 1;k <= n;++k)
v[i][j] += b[i][k] * inv[k][j];
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= n;++j)
if(fabs(v[j][i]) > eps)
e[i][j] = 1;
for(register int i = 1;i <= n;++i)
{
memset(vis,0,sizeof vis);
if(!dfs(i))
{
puts("NIE");
return 0;
}
}
for(register int i = 1;i <= n;++i)
memset(vis,0,sizeof vis),dfs(i,i);
for(register int i = 1;i <= n;++i)
ans[match[i]] = i;
puts("TAK");
for(register int i = 1;i <= n;++i)
printf("%d\n",ans[i]);
}