自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 21:56:30，当前版本为作者最后更新于2021-07-09 13:46:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

$\text{Update2023.4.13}$：修复一个错误。

题意

给 $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)$。

代码：

#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~