一、题目
二、解法
这个题比较小清新。
先考虑二维的情况，我们应该如何染色？如果我们想染 ((a,b)) ，其实可以拆成 (a) 次 ((1,b)) ，所以每次花费 (1) 的染色是最优的。然后可以让 (b) 尽可能大，所以每次都只会染一行或者一列，现在就变成套路了，如果 ((i,j)) 需要染色就把 (i) 行 (j) 列连边，然后问题变成了最小点覆盖，求最大匹配即可。
但是现在问题是在三维空间，其实是可以类比二维空间的。最优策略还是每次只花费 (1) ，所以一定是某一维取 (1) ，剩下两维都取最大，但是我们并没有所谓三分图匹配，我们只能解决二分图的情况。
注意到 (abcleq 5000) ，所以 (min(a,b,c)leq 17) ，枚举较小的那一维，是直接染色整层还是暂时不处理。现在我把较小的一维叫层，剩下的叫行和列，对于没有处理的层，我们需要染色点的行列连边，我们还是每次只染一行或者一列（注意现在我们可以取满所有的层），类似地跑最大匹配即可。
震惊，( t dinic) 就算加了当前弧优化也会 ( t T) 飞，还好有 (O_2)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int M = 205;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n[4],m,s,t,tot,ans,dis[M],zy[M],cur[M],f[M],a[4][M*M];
struct edge
{
int v,c,next;
edge(int V=0,int C=0,int N=0) : v(V) , c(C) , next(N) {}
}e[M*M];
void add(int u,int v,int c)
{
e[++tot]=edge(v,c,f[u]),f[u]=tot;
e[++tot]=edge(u,0,f[v]),f[v]=tot;
}
int bfs()
{
queue<int> q;
memset(dis,0,sizeof dis);
q.push(s);dis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
if(u==t) return 1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==0 && e[i].c>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int ept)
{
if(u==t) return ept;
int flow=0,tmp=0;
for(int &i=cur[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1 && e[i].c>0)
{
tmp=dfs(v,min(ept,e[i].c));
if(!tmp) continue;
flow+=tmp;
e[i].c-=tmp;
e[i^1].c+=tmp;
ept-=tmp;
if(!ept) break;
}
}
return flow;
}
void ppl(int s)
{
int tmp=0;
for(int i=0;i<n[1];i++)
{
if(s&(1<<i)) zy[i+1]=1,tmp++;
else zy[i+1]=0;
}
s=0;t=n[2]+n[3]+1;tot=1;
for(int i=0;i<=t;i++) f[i]=0;
for(int i=1;i<=m;i++)
if(!zy[a[1][i]])
add(a[2][i],a[3][i]+n[2],1);
for(int i=1;i<=n[2];i++) add(s,i,1);
for(int i=n[2]+1;i<=n[2]+n[3];i++) add(i,t,1);
while(bfs())
{
for(int i=s;i<=t;i++) cur[i]=f[i];
tmp+=dfs(s,inf);
}
ans=min(ans,tmp);
}
signed main()
{
T=read();
while(T--)
{
ans=inf;m=0;
n[1]=read();n[2]=read();n[3]=read();
for(int i=1;i<=n[1];i++)
for(int j=1;j<=n[2];j++)
for(int k=1;k<=n[3];k++)
{
int x=read();
if(!x) continue;
a[1][++m]=i;
a[2][m]=j;
a[3][m]=k;
}
if(n[2]<min(n[1],n[3])) swap(n[1],n[2]),swap(a[1],a[2]);
else if(n[3]<min(n[1],n[2])) swap(n[1],n[3]),swap(a[1],a[3]);
for(int i=0;i<(1<<n[1]);i++)
ppl(i);
printf("%d
",ans);
}
}