题解 P4100【[HEOI2013]钙铁锌硒维生素】
cyffff
·
·
题解
\text{Link}
## 题意
给 $n$ 个线性无关的向量集 $A_1,A_2\cdot\cdot\cdot A_n$ 和一个向量集 $B_1,B_2\cdot\cdot\cdot B_n$，求字典序最小的排列 $p$ 使得将任意的一个 $A_i$ 替换为 $B_{p_i}$ 后，新的向量集依然线性无关。
$n\le300$。
## 思路
先介绍一下基础知识，会的可以跳过这一段。
**线性组合**：设在域 $P$ 中有向量集 $A_1,A_2\cdot\cdot\cdot A_n$，若有向量 $B=\sum_{i=1}^n k_iA_i$，其中 $k\in P$，则 $B$ 是向量集 $A$ 的一个线性组合。
**线性相关，线性无关**：设在域 $P$ 中有向量集 $A_1,A_2\cdot\cdot\cdot A_{n}$，若有一向量 $A_x$ 为剩余 $n-1$ 个向量的线性组合，则称这 $n$ 个向量线性相关；反之，则称这 $n$ 个向量线性无关。
**定理** 若有 $n$ 维向量集 $A_1,A_2\cdot\cdot\cdot A_{n}$ 线性无关，则所有 $n$ 维向量都可表示为其线性组合。
即 $n$ 元 $1$ 次方程组，有 $n$ 个方程，可解出唯一解 $k_1,k_2\cdot\cdot\cdot k_n$。
回到这题，我们构建矩阵：
$A=\begin{bmatrix}A_1,A_2,\cdot \cdot \cdot A_n\end{bmatrix},B=\begin{bmatrix}B_1,B_2,\cdot \cdot \cdot B_n\end{bmatrix}$。
由于 $B_{i,j}=\sum_{k=1}^n R_{i,k}A_{k,j}$，我们可以把转换系数 $R$ 也看做矩阵，则有 $B=RA$，$R=BA^{-1}$。
此时若 $R_{i,j}\ne0$，则 $A_i$ 可以转为 $B_j$；反之则不能，因为 $R_{i,j}=0$ 时，$B_j$ 是 $A_1\cdot\cdot\cdot A_{i-1}A_{i+1}\cdot\cdot\cdot A_n$ 的线性组合。
那么当 $R_{i,j}\ne0$ 时，由 $i$ 向 $j$ 连边建立二分图。
剩余的问题就是二分图最小字典序完美匹配。可以先跑出一组匹配，再使字典序最小。
则在原匹配中有一条增广路径的环上有边 $(u,v)$ 时 $(u,v)$ 的匹配合法，于是找到最小的环即可。
时间复杂度 $O(n^3)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int N=300+10;
const double eps=1e-7;
int n;
struct Matrix{
double a[N][N];
inline double* operator[](const int &x){
return a[x];
}
Matrix(){
memset(a,0,sizeof(a));
}
inline void epsilon(){
for(int i=1;i<=n;i++)
a[i][i]=1;
}
inline friend Matrix operator*(const Matrix &a,const Matrix &b){
Matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c[i][j]+=a.a[i][j]*b.a[j][k];
return c;
}
inline void swapp(int i,int j){
swap(a[i],a[j]);
}
}a,b,r;
int match[N];
bool vis[N];
inline bool dfs(int x){
for(int t=1;t<=n;t++){
if(!vis[t]&&fabs(r[x][t])>eps){
vis[t]=true;
if(!match[t]||dfs(match[t])){
match[t]=x;
return true;
}
}
}
return false;
}
inline int dfs(int x,int tp){
for(int t=1;t<=n;t++){
if(!vis[t]&&fabs(r[x][t])>eps){
vis[t]=true;
if(match[t]==tp||(match[t]>tp&&dfs(match[t],tp))){
match[t]=x;
return t;
}
}
}
return 0;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[j][i]=(double)read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[j][i]=(double)read();
r.epsilon();
for(int i=1;i<=n;i++){
int k=i;
for(int j=i+1;j<=n;j++)
if(fabs(a[j][i])>fabs(a[k][i]))
k=j;
if(fabs(a[k][i])<eps){
puts("NIE");
return 0;
}
if(k!=i)
a.swapp(i,k),
b.swapp(i,k);
double x=a[i][i];
for(int j=1;j<=n;j++){
a[i][j]/=x,b[i][j]/=x;
}
for(int j=1;j<=n;j++)
if(i!=j){
double res=a[j][i];
for(int k=1;k<=n;k++)
a[j][k]-=a[i][k]*res,
b[j][k]-=b[i][k]*res;
}
}
r=b;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(!dfs(i))
return puts("NIE"),0;
}
puts("TAK");
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
write(dfs(i,i)),putc('\n');
}
flush();
}
```
再见 qwq~