[HEOI2013]钙铁锌硒维生素

第一行包含一个正整数n。
接下来n行，每行n个整数，表示第1套厨师机器人做的菜每一斤提供的每种营养。
再接下来n行，每行n个整数，表示第2套厨师机器人做的菜每一斤提供的每种营养。
1 ≤ n ≤ 300，所有出现的整数均非负，且不超过10,000。

第一行是一个字符串，如果无法完成任务，输出“NIE”，否则输出“TAK”并跟着n行，第i行表示第i个第1套机器人的备份是哪一个第2套机器人。
为了避免麻烦，如果有多种可能的答案，请给出字典序最小的那一组。

C++(clang++11) 解法, 执行用时: 258ms, 内存消耗: 3176K, 提交时间: 2021-02-13 16:07:08

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define mod 999911657
using namespace std;
const double eps=1e-6;
typedef long long ll;
int n,ans;
ll A[310][610],B[310][310],C[310][310];
int vis[310],from[310],to[310];
ll pm(ll x,ll y)
{
    ll z=1;
    while(y)
    {
        if(y&1) z=z*x%mod;
        x=x*x%mod,y>>=1;
    }
    return z;
}
int rd()
{
    int ret=0;  char gc=getchar();
    while(gc<'0'||gc>'9') gc=getchar();
    while(gc>='0'&&gc<='9')   ret=ret*10+gc-'0',gc=getchar();
    return ret;
}
int dfs1(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(C[i][x]&&!vis[i])
        {
            vis[i]=1;
            if(!from[i]||dfs1(from[i]))
            {
                to[x]=i,from[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int dfs2(int x,int y)
{
    for(int i=1;i<=n;i++)
    {
        if(C[i][x]&&!vis[i])
        {
            vis[i]=1;
            if(from[i]==y||(from[i]>y&&dfs2(from[i],y)))
            {
                from[i]=x,to[x]=i;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    n=rd();
    int i,j,k;
    for(i=1;i<=n;i++)    for(j=1;j<=n;j++)    A[i][j]=rd(),A[i][j+n]=(i==j);
    for(i=1;i<=n;i++)    for(j=1;j<=n;j++)    B[i][j]=rd();
    ll t;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)    if(A[j][i])
        {
            for(k=1;k<=2*n;k++)  swap(A[i][k],A[j][k]);
            break;
        }
        t=pm(A[i][i],mod-2);
        for(k=i;k<=2*n;k++)  A[i][k]=A[i][k]*t%mod;
        for(j=1;j<=n;j++)    if(i!=j)
        {
            t=A[j][i];
            for(k=1;k<=2*n;k++)  A[j][k]=(A[j][k]-t*A[i][k]%mod+mod)%mod;
        }
    }
    for(i=1;i<=n;i++)    for(j=1;j<=n;j++)    for(k=1;k<=n;k++)    C[i][j]=(C[i][j]+B[i][k]*A[k][j+n])%mod;
    for(i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        ans+=dfs1(i);
    }
    if(ans<n)
    {
        printf("NIE");
        return 0;
    }
    printf("TAK\n");
    for(i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        dfs2(i,i);
    }
    for(i=1;i<=n;i++)    printf("%d\n",to[i]);
    return 0;
}

详情