[文章目录]
Description
给你n个n维向量。然后，再给你n个n维向量。询问能否对于每个先给的向量缺失后都能否用后给不同的向量替换，并且使原来n*n的向量构成的矩阵仍然满秩。n<=300
首先考虑，如果原n维向量不满秩，那么肯定无解。如果原来矩阵是满秩的，那么，如果一个备用向量能替换原矩阵里的向量集合符合该向量能够被这个集合里的向量集合线性表示。所以假设这个向量为1*n的矩阵b。那么x*a=b，a为n*n原矩阵。那么x就是线性表示的解。如果该位上！=0说明能够替换该向量。将每个替换向量的线性解构成一个矩阵X，那么X*A=B。B为替换向量的n*n矩阵。然后，X=B*A-1
那么逆矩阵的求法：
用到了一个性质：一个矩阵有逆矩阵当且仅当这个矩阵满秩。
将A放到一个n*2n的矩阵的左面，然后把一个单位矩阵放到右面。然后进行高斯消元，将左面的矩阵削成单位矩阵，右面那半就变成A矩阵的逆矩阵了。
然后，我们就能求出X矩阵，从而知道每个备份向量能够替换的向量的集合。然后跑一边最大匹配。如果为n，那么有解。然后最小字典序的话，将每个向量的匹配进行移动。如果找到一个比当前的解字典序更小的向量能够交换就交换。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,ans[310];
double map[310][610];
double b[310][310],c[310][310];
void SW(int x,int y)
{
for(int i=1;i<=2*n;i++)
swap(map[x][i],map[y][i]);
}
int flag[610];
bool vis[610];
bool dfs1(int x)
{
for(int i=1;i<=n;i++)
{
if(c[i][x]>1e-5&&!vis[i])
{
vis[i]=true;
if(flag[i]==0||dfs1(flag[i]))
{
flag[i]=x;
return true;
}
}
}
return false;
}
bool dfs2(int x,int pre)
{
for(int i=1;i<=n;i++)
{
if(c[i][x]>1e-5&&!vis[i])
{
vis[i]=true;
if(flag[i]==pre||(flag[i]>pre&&dfs2(flag[i],pre)))
{
flag[i]=x; ans[x]=i;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lf",&map[i][j]);
for(int i=1;i<=n;i++)
map[i][n+i]=1.0;
for(int i=1;i<=n;i++)
{
double tmp=1e-5;int now=-1;
for(int j=i;j<=n;j++)
if(fabs(map[j][i])>tmp) {now=j;break;}
if(now==-1){puts("NIE"); return 0;}
SW(now,i);
for(int j=2*n;j>=i;j--) map[i][j]/=map[i][i];
for(int j=1;j<=n;j++)
if(j!=i)
for(int ii=2*n;ii>=i;ii--)
map[j][ii]-=map[j][i]*map[i][ii];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lf",&b[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
c[i][j]+=b[i][k]*map[k][j+n];
if(fabs(c[i][j])>1e-5) c[i][j]=100.0;
else c[i][j]=-100.0;
}
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(!dfs1(i)) {puts("NIE"); return 0;}
}
puts("TAK");
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
dfs2(i,i);
}
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}