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

发表于 | 分类于 | 6

题意可转化为：给定 2n 个行向量，分别为 A1…n 和 B1…n，求一个字典序最小的 1…n 的排列 P，满足 A1…i−1,BPi,Ai+1…n 线性不相关。

设 Vi,j 表示用 A1…n 线性组合出 Bi 时 Aj 的系数。
那么有 Bi,j=n∑k=1Vi,kAk,j，即 B=VA，即 V=BA−1。
那么矩阵求逆求出 V 之后，若 Vi,j≠0，则连接 Bi,Aj。这是因为若不满足此条件，意味着用除 Aj 之外的行向量可以表示出 Bi，交换后便不满足线性无关；否则易得其仍然线性无关。

如何求字典序最小的二分图完美匹配？
首先任意求出一组匹配，然后枚举 1…n，分别贪心地强制选取目前最小的匹配点，并查看是否还可匹配成功。
需要使用匈牙利算法实现，复杂度 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