题意可转化为:给定 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 |
|