判定有解是一个比较经典的Hall定理。
也即,将 \(a\) 看作正数,将 \(b\) 看作负数,那么一个在 \((i,j,k)\) 的 \(1\),可以与一个在 \((a,b,c)(a\ge i,b\ge j,c\ge k)\) 的 \(-1\) 进行匹配。
根据 Hall 定理,有 \(|N(S)|\ge |S|\),转化后就是,选出一些 \(1\) 后,对所有的被其偏序的 \(-1\) 个数之和大于等于选出的 \(1\) 的个数。
那么我们在 \(N(S)\) 确定时肯定要最大化 \(|S|\),因此令 \(c_{i,j}=b_{i,j}-a_{i,j}\),问题变为对于所有的满足满足 \((a,b,c)\) 被选了,则所有 \((i,j,k)(i\le a,j\le b,k\le c)\) 的点都被选的选点方案,点权和不大于零。
转化为关于最大值的计算,考虑DP。
注意到,随着第一维 \(i\) 的增加,不妨将平面上的限制看作一条 \((m-1,0)\to (0,k-1)\) 轮廓线,那么这条线是在不断上移的(也即框住的点越来越少)。
用一个恰有 \(k\) 个 \(1\) 的二进制数记录一条轮廓线,从 \((m-1,0)\) 开始走,遇到 \(1\) 就增加第二维,遇到 \(0\) 就减少第一维,转移就是将一对 \(01\) 改为 \(10\),这样恰好少框住一个点,于此同时再算一下本层框住点的点权和即可。
实现上,由于轮廓线是上移的过程,所以不妨维护下方没框住的点的点权和,由于全局和为零,因此改为维护答案的相反数的最小值即可。
#include<bits/stdc++.h>
using namespace std;
#define N 10505
#define int long long
int f[1<<12],g[1<<12],n,m,k,a[N][6][6];
void sol(){cin>>n>>m>>k;for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(int t=0;t<k;++t)cin>>a[i][j][t];for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(int t=0,x;t<k;++t)cin>>x,a[i][j][t]=x-a[i][j][t];vector<int>stu;for(int i=0;i<(1<<m+k);++i)if(__builtin_popcount(i)==k)stu.push_back(i);memset(f,0x3f,sizeof f);f[(1<<k)-1]=0;for(int i=0;i<n;++i){memset(g,0,sizeof g);for(int j:stu)if(f[j]<1e18){for(int t=1,x=m-1,y=0;t<m+k;++t){if(((j>>t)&1)==0&&((j>>t-1)&1)){//上移f[j^(3<<t-1)]=min(f[j^(3<<t-1)],f[j]);g[j^(3<<t-1)]=g[j]+a[i][x][y];}if((j>>t-1)&1)++y;else --x;}f[j]+=g[j];}}for(int i:stu)if(f[i]<0){cout<<"NIE\n";return ;}cout<<"TAK\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=0;cin>>t;while(t--)sol();
}