Description
银河队选手名单出来了！小林，作为特聘的营养师，将负责银河队选手参加 宇宙比赛的饮食。众所周知，前往宇宙的某个星球，通常要花费好长好长的时间，人体情况在这之间会发生变化，因此，需要根据每天的情况搭配伙食，来保证营养。小林把人体需要的营养分成了n种，这些营养包括但不限于铁，钙。他准备了2套厨师机器人，一套厨师机器人有n个，每个厨师机器人只会做一道菜，这道菜一斤能提供第i种营养xi微克。想要吃这道菜的时候，只要输入一个数，就能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害，每个机器人还有防过量摄入药，只要输入一个数，就能生成一定剂量的药，吃了这些药，就能减少相当于食用对应数目的这道菜提供的营养。 小林之所以准备2套厨师机器人，正是因为旅途漫漫，难以预计，也许某一个厨师机器人在途中坏掉，要是影响了银河队选手的身体，就不好了。因此，第2套厨师机器人被用来做第1套的备用。小林需要为每一个第1套厨师机器人选一个第2套厨师机器人作备份，使得当这个机器人坏掉时，用备份顶替，整套厨师机器人仍然能搭配出任何营养需求，而且，每个第2套厨师机器人只能当一个第1套厨师机器人的备份。 Input
第一行包含一个正整数n。接下来n行，每行n个整数，表示第 1套厨师机器人做的菜每一斤提供的每种营养。再接下来n行，每行n个整数，表示第2套厨师机器人做的菜每一斤提供的每种营养。 Output
第一行是一个字符串，如果无法完成任务，输出“NIE”，否则输 出“TAK”，并跟着n行，第i行表示第i个第1套机器人的备份是哪一个第2套机器人。为了避免麻烦，如果有多种可能的答案，请给出字典序最小的那一组。
对于每一个 bi 求出他能替换哪些向量 aj ，然后就变成了字典序最小的二分图完备匹配问题。 把向量 a 组成矩阵A，然后求 xA=bi ，也就是 bi=x1a1+x2a2+⋯+xnan 。如果 xj 不为零， bi 可以替换 aj 。把 b 拼成矩阵B，求出 C=B∗A−1 就是二分图的邻接矩阵。 在二分图上先求出一个完备匹配，然后从小到大考虑每个位置连的边，选择一条最小的而且不会影响之前的匹配的路径进行更换。 原题数据貌似不保证矩阵 A <script type="math/tex" id="MathJax-Element-1193">A</script>可逆，需要判断。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long const int p=100000007; int n,f[310],vis[310],ans[310],ok=1; int pow(int base,int x) { int ret=1; while (x) { if (x&1) ret=(LL)ret*base%p; base=(LL)base*base%p; x>>=1; } return ret; } struct mat { int a[310][310]; void rd() { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); } mat operator * (const mat &m) const { mat ret; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { ret.a[i][j]=0; for (int k=1;k<=n;k++) ret.a[i][j]=(ret.a[i][j]+(LL)a[i][k]*m.a[k][j]%p)%p; } return ret; } mat inv() { mat ret; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ret.a[i][j]=(i==j); for (int i=1;i<=n;i++) { int x; x=-1; for (int j=i;j<=n;j++) if (a[j][i]) { x=j; break; } if (x==-1) { ok=0; return ret; } if (x!=i) for (int j=1;j<=n;j++) { swap(a[i][j],a[x][j]); swap(ret.a[i][j],ret.a[x][j]); } x=pow(a[i][i],p-2); for (int j=1;j<=n;j++) { a[i][j]=(LL)a[i][j]*x%p; ret.a[i][j]=(LL)ret.a[i][j]*x%p; } for (int j=1;j<=n;j++) if (j!=i) { x=a[j][i]; for (int k=1;k<=n;k++) { a[j][k]=(a[j][k]-(LL)a[i][k]*x%p+p)%p; ret.a[j][k]=(ret.a[j][k]-(LL)ret.a[i][k]*x%p+p)%p; } } } return ret; } }a,b,c; int dfs1(int u) { for (int v=1;v<=n;v++) if (c.a[v][u]&&!vis[v]) { vis[v]=1; if (!f[v]||dfs1(f[v])) { f[v]=u; return 1; } } return 0; } int dfs2(int u,int from) { for (int v=1;v<=n;v++) if (c.a[v][u]&&!vis[v]) { vis[v]=1; if (f[v]==from||(f[v]>from&&dfs2(f[v],from))) { f[v]=u; return 1; } } return 0; } int main() { int cnt=0; scanf("%d",&n); a.rd(); b.rd(); c=b*a.inv(); if (!ok) { printf("NIE\n"); return 0; } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) vis[j]=0; if (dfs1(i)) cnt++; } if (cnt<n) printf("NIE\n"); else { printf("TAK\n"); for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) vis[j]=0; dfs2(i,i); } for (int i=1;i<=n;i++) ans[f[i]]=i; for (int i=1;i<=n;i++) printf("%d\n",ans[i]); } }