本文共 1681 字，大约阅读时间需要 5 分钟。

一、题目

二、解法

这个题比较小清新。

先考虑二维的情况，我们应该如何染色？如果我们想染 \((a,b)\) ，其实可以拆成 \(a\) 次 \((1,b)\) ，所以每次花费 \(1\) 的染色是最优的。然后可以让 \(b\) 尽可能大，所以每次都只会染一行或者一列，现在就变成套路了，如果 \((i,j)\) 需要染色就把 \(i\) 行 \(j\) 列连边，然后问题变成了最小点覆盖，求最大匹配即可。

但是现在问题是在三维空间，其实是可以类比二维空间的。最优策略还是每次只花费 \(1\) ，所以一定是某一维取 \(1\) ，剩下两维都取最大，但是我们并没有所谓三分图匹配，我们只能解决二分图的情况。

注意到 \(abc\leq 5000\) ，所以 \(\min(a,b,c)\leq 17\) ，枚举较小的那一维，是直接染色整层还是暂时不处理。现在我把较小的一维叫层，剩下的叫行和列，对于没有处理的层，我们需要染色点的行列连边，我们还是每次只染一行或者一列（注意现在我们可以取满所有的层），类似地跑最大匹配即可。

震惊，\(\tt dinic\) 就算加了当前弧优化也会 \(\tt T\) 飞，还好有 \(O_2\)

#include 
   
    #include 
    
     #include 
     
      #include 
      
       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
       
         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