洛谷 4100 「HEOI2013」钙铁锌硒维生素

题意可转化为:给定 2n 个行向量,分别为 A1nB1n,求一个字典序最小的 1n 的排列 P,满足 A1i1,BPi,Ai+1n 线性不相关。

Vi,j 表示用 A1n 线性组合出 BiAj 的系数。
那么有 Bi,j=nk=1Vi,kAk,j,即 B=VA,即 V=BA1
那么矩阵求逆求出 V 之后,若 Vi,j0,则连接 Bi,Aj。这是因为若不满足此条件,意味着用除 Aj 之外的行向量可以表示出 Bi,交换后便不满足线性无关;否则易得其仍然线性无关。

如何求字典序最小的二分图完美匹配?
首先任意求出一组匹配,然后枚举 1n,分别贪心地强制选取目前最小的匹配点,并查看是否还可匹配成功。
需要使用匈牙利算法实现,复杂度 O(n3)

代码:

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
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]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment