BZOJ 3140:[Hnoi 2013]消毒

まず簡単にテーマを分析して、1つのとても良い策略を見つけることができて、つまり毎回1つの切面を選んで消毒して、費用は1です.
それから私たちは欲張りを考えて、毎回一番多い面を探して、それを消して、注文がないまで.
明らかにそうするのは間違っているQQQです
列挙は他のアルゴリズムの基礎とすることができる.
a<=b<=cとしてもよいので,各層に木が消毒されていることを列挙し,古典的な行列被覆点問題となり,最小点被覆=最大整合,直接二分図整合でよい.
しかし、これはリスクがあります.最悪の場合、複雑度は3*2^17*17*17で、爆発する可能性があります.
だから枝を切るとか
ハンガリーアルゴリズムには不思議な特性があるため、ダイナミックエッジをサポートしています.つまり、原図で拡大することができます.
そこで私たちは現在の層を検索する時、もしこの層が消毒すれば、原図は変わらないで、さもなくば原図の上でエッジを追加して、答えを広く更新します.
そしてRANK 1辛
この問題はあまりにも水都木が最適化していると思っているのではないでしょうかQQQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5000+5;
const int inf=1e9;
int v[N],a,b,c;
int id(int x,int y,int z){
	return (z-1)*b*c+(x-1)*c+y;
}
int x(int idx){
	return (idx-1)%(b*c)/b+1;
}
int y(int idx){
	return (idx-1)%c+1;
}
int z(int idx){
	return (idx-1)/(b*c)+1;
}
bool vis[50];
bool g[50][50][50];
int linked[50][50],matched[50][50];
int layer;
bool match(int u){
	for(int v=1;v<=c;v++){
		if(!g[layer][u][v]||vis[v])continue;
		vis[v]=true;
		if(!linked[layer][v]||match(linked[layer][v])){
			linked[layer][v]=u;matched[layer][u]=v;
			return true;
		}
	}
	return false;
}
int ans;
void dfs(int z,int tmp,int last){
	if(tmp>=ans)return;
	if(z>a)ans=min(ans,tmp);
	else{
		dfs(z+1,tmp+1,last);
		layer=z;
		for(int x=1;x<=b;x++)
		for(int y=1;y<=c;y++){
			g[z][x][y]=g[last][x][y];
			if(v[id(x,y,z)])
			g[z][x][y]=1;
		}
		for(int y=1;y<=c;y++)
		linked[z][y]=linked[last][y];
		for(int x=1;x<=b;x++)
		matched[z][x]=matched[last][x];
		for(int x=1;x<=b;x++)
		if(!matched[z][x]){
			for(int y=1;y<=c;y++)
			vis[y]=0;
			tmp+=match(x);
		}
		dfs(z+1,tmp,z);
	}
}
int main(){
	//freopen("a.in","r",stdin);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&a,&b,&c);
		for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
		for(int k=1;k<=c;k++)
		scanf("%d",&v[id(j,k,i)]);
		ans=inf;
		dfs(1,0,0);
		printf("%d
",ans);
	}
	return 0;
}