[BZOJ3168] [Heoi2013]钙铁锌硒维生素
Description
银河队选手名单出来了！小林，作为特聘的营养师，将负责银河队选手参加宇宙比赛的饮食。众所周知，前往宇宙的某个星球，通常要花费好长好长的时间，人体情况在这之间会发生变化，因此，需要根据每天的情况搭配伙食，来保证营养。小林把人体需要的营养分成了n种，这些营养包括但不限于铁，钙。他准备了2套厨师机器人，一套厨师机器人有n个，每个厨师机器人只会做一道菜，这道菜一斤能提供第i种营养xi微克。想要吃这道菜的时候，只要输入一个数，就能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害，每个机器人还有防过量摄入药，只要输入一个数，就能生成一定剂量的药，吃了这些药，就能减少相当于食用对应数目的这道菜提供的营养。小林之所以准备2套厨师机器人，正是因为旅途漫漫，难以预计，也许某一个厨师机器人在途中坏掉，要是影响了银河队选手的身体，就不好了。因此，第2套厨师机器人被用来做第1套的备用。小林需要为每一个第1套厨师机器人选一个第2套厨师机器人作备份，使得当这个机器人坏掉时，用备份顶替，整套厨师机器人仍然能搭配出任何营养需求，而且，每个第2套厨师机器人只能当一个第1套厨师机器人的备份。
Input
第一行包含一个正整数n。接下来n行，每行n个整数，表示第1套厨师机器人做的菜每一斤提供的每种营养。再接下来n行，每行n个整数，表示第2套厨师机器人做的菜每一斤提供的每种营养。1≤n≤300，所有出现的整数均非负，且不超过10,000。
Output
第一行是一个字符串，如果无法完成任务，输出“NIE”，否则输出“TAK”并跟着n行，第i行表示第i个第1套机器人的备份是哪一个第2套机器人。为了避免麻烦，如果有多种可能的答案，请给出字典序最小的那一组。
Sample Input
3
1 0 0
0 1 0
0 0 1
2 3 0
0 7 8
0 0 9
Sample Output
TAK
1
2
3
试题分析
推荐博客：Link
首先A中的N个向量可以表示出N种营养，所以A中的向量是线性无关的。
那么也就是要求B替换A后仍旧线性无关。
那么只需要求(B_i=sum c_j A_j)，那么如果(c_j)是0，说明不用(A_j)就可以表出(B_i)，所以(A_j)是不能被(B_j)替换的，反之亦然。
说明存在矩阵(C)满足：
于是求出(A)的逆矩阵就可以建立二分图并贪心匹配了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
inline int read(){
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int INF = 2147483600;
const int MAXN = 100010;
const int Mod = 999911657;
int N; bool Nxt[501][501];
bool vis[501]; int fa[MAXN+1];
inline LL Pow(LL A,LL B){
LL res=1;
while(B){
if(B&1) res=res*A%Mod;
A=A*A%Mod; B>>=1;
} return res;
}
struct Matrix{
int A[301][301]; int x,y;
inline void init(int xx,int yy){
memset(A,0,sizeof(A));
x=xx; y=yy;
}
inline Matrix Get_Inv(){
Matrix Inv; Inv.init(x,y);
for(int i=1;i<=x;i++) Inv.A[i][i]=1;
for(int i=1;i<=x;i++){
int r=i;
for(int j=i;j<=x;j++)
if(A[j][i]) {r=j; break;}
if(i!=r) for(int j=1;j<=y;j++){
swap(A[i][j],A[r][j]);
swap(Inv.A[i][j],Inv.A[r][j]);
} LL inv=Pow(A[i][i],Mod-2); for(int j=1;j<=y;j++){
A[i][j]=1LL*A[i][j]*inv%Mod;
Inv.A[i][j]=1LL*Inv.A[i][j]*inv%Mod;
} for(int j=1;j<=x;j++){
if(j==i) continue;
LL tp=(Mod-A[j][i])%Mod;
for(int k=1;k<=y;k++){
(A[j][k]+=1LL*tp*A[i][k]%Mod)%=Mod;
(Inv.A[j][k]+=1LL*tp*Inv.A[i][k]%Mod)%=Mod;
}
}
} return Inv;
}
inline void Get(int xx,int yy){
init(xx,yy);
for(int i=1;i<=xx;i++){
for(int j=1;j<=yy;j++)
A[i][j]=read();
} return ;
}
}A,B,C;
Matrix operator * (Matrix A,Matrix B){
Matrix C; if(A.x==B.y&&A.y!=B.x) swap(A,B);
C.init(A.x,B.y);
for(int i=1;i<=A.x;i++){
for(int j=1;j<=B.y;j++)
for(int k=1;k<=A.y;k++)
(C.A[i][j]+=1LL*A.A[i][k]*B.A[k][j]%Mod)%=Mod;
} return C;
}
inline bool DFS(int k){
for(int i=1;i<=N;i++){
if(Nxt[k][i]&&!vis[i]){
vis[i]=true;
if(!fa[i]||DFS(fa[i])){
fa[i]=k; return true;
}
}
} return false;
}
inline bool DFS2(int k,int Fa){
for(int i=1;i<=N;i++){
if(Nxt[k][i]&&!vis[i]){
vis[i]=true;
if(fa[i]==Fa || fa[i]>Fa && DFS2(fa[i],Fa)){
fa[i]=k; return true;
}
}
} return false;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
N=read(); A.Get(N,N),B.Get(N,N);
Matrix Inv=(A.Get_Inv());
C=B*Inv;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++) Nxt[i][j]=(bool)C.A[j][i];
}
for(int i=1;i<=N;i++){
memset(vis,false,sizeof(vis));
if(!DFS(i)){puts("NIE"); return 0;}
} puts("TAK");
for(int i=1;i<=N;i++){
memset(vis,false,sizeof(vis));
DFS2(i,i);
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(fa[j]==i)
printf("%d
",j);
}
}
return 0;
}