傳送門

Description

最近在生物實驗室工作的小T遇到了大麻煩。 由于實驗室最近升級的緣故，他的分格實驗皿是一個長方體,其尺寸為abc，a、b、c 均為正整數。為了實驗的方便，它被劃分為abc個單位立方體區域，每個單位立方體尺寸為111。用(i,j,k)標識一個單位立方體，1 <=i<=a，1<=j<=b，1<=k<=c。這個實驗皿已經很久沒有人用了，現在，小T被導師要求將其中一些單位立方體區域進 行消毒操作（每個區域可以被重復消毒）。

而由于嚴格的實驗要求，他被要求使用一種特定 的F試劑來進行消毒。 這種F試劑特別奇怪，每次對尺寸為xyz的長方體區域（它由xyz個單位立方體組 成）進行消毒時，只需要使用min{x,y,z}單位的F試劑。F試劑的價格不菲，這可難倒了小 T。

現在請你告訴他，最少要用多少單位的F試劑。(注：min{x,y,z}表示x、y、z中的最小 者。)

Input

第一行是一個正整數D，表示數據組數。接下來是D組數據，每組數據開頭是三個數a,b,c表示實驗皿的尺寸。接下來會出現a個b 行c列的用空格隔開的01矩陣，0表示對應的單位立方體不要求消毒，1表示對應的單位立方體需要消毒；例如，如果第1個01矩陣的第2行第3列為1，則表示單位立方體(1,2,3)需要被消毒。輸入保證滿足abc<=5000,T<=3。

Output

僅包含D行，每行一個整數，表示對應實驗皿最少要用多少單位 的F試劑。

Sample Input

1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0

Sample Output

3

Solution

很明顯最優的方案一定是選擇(1,b,c)或(a,1,c)或(a,b,1)
這樣便轉化為三維最小覆蓋（不過沒啥用）
但我們只會做二維最小覆蓋（二分圖），那么就考慮一維暴力，剩下的用二分圖
由于\(a*b*c\leq5000\) 所以其中最小的一維一定小于17
所以最終的做法就是最小的一維\(2^{k}（k\leq17）\)暴力，記錄剩下的用二分圖解決

Code

//By Menteur_Hxy #include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) using namespace std; typedef long long LL;LL read() {LL x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const int N=5010,INF=0x3f3f3f3f; bool vis[N]; int a,b,c,fla,ans,tot; int bx[N],by[N],bz[N],map[N][N],mat[N]; vector <int> vx[N];inline void add(int x,int y,int z) {if(fla==2) swap(x,y);else if(fla==3) swap(x,z);bx[++tot]=x,by[tot]=y,bz[tot]=z;//bx其實沒用233vx[x].push_back(tot); } bool dfs2(int u) {F(v,1,c) if(map[u][v]&&!vis[v]) {vis[v]=1;if(!mat[v] || dfs2(mat[v])) {mat[v]=u;return 1;}}return 0; }void dfs1(int pos,int used) {if(pos==a+1) {int res=used;memset(mat,0,sizeof(mat));F(i,1,b) {memset(vis,0,sizeof(vis));if(dfs2(i)) res++;}ans=min(ans,res);return ;}dfs1(pos+1,used+1);int siz=vx[pos].size();F(i,0,siz-1) {int now=vx[pos][i];map[by[now]][bz[now]]++;}dfs1(pos+1,used);F(i,0,siz-1) {int now=vx[pos][i];map[by[now]][bz[now]]--;} }int main() {int cas=read();while(cas--) {tot=0; ans=INF;a=read(),b=read(),c=read();if(a<=b&&a<=c) fla=1;else if(b<=a&&b<=c) fla=2;else fla=3;F(i,1,a) F(j,1,b) F(k,1,c) if(read()) add(i,j,k);if(fla==2) swap(a,b);else if(fla==3) swap(a,c);dfs1(1,0);printf("%d\n",ans);F(i,1,a) vx[i].clear();}return 0; }

轉載于:https://www.cnblogs.com/Menteur-Hxy/p/9505412.html

總結

以上是生活随笔為你收集整理的[luogu3231 HNOI2013] 消毒 (二分图最小点覆盖)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。