題目描述

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

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

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

輸入輸出格式

輸入格式：

?

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：?復制 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 輸出樣例#1：?復制 3

說明

對于區域(1,1,3)-(2,2,4)和(1,1,1)-(4,4,1)消毒，分別花費2個單位和1個單位的F試劑。

題解

　　我們先來考慮一下二維的情況

　　對于一整塊需要染色的部分，我們可以選擇一條一條地去染色（也就是說使每一次的最小值為$1$，另一個就可以隨便取了），那么答案肯定不會比直接一塊染更差

　　比方說$(1,1)$到$(2,3)$都有，你直接整塊染或者每次染一行實際上答案是一樣的

　　所以我們對每一個點的$x->y$連一條邊，然后要求一個最小點覆蓋，等于最大匹配

　　然后怎么考慮三維的情況？我們可不會三分圖，那個可沒有多項式解法

　　考慮到$a,b,c$中最小的不會超過17（因為$17^3=4913$），所以我們可以考慮枚舉這一維，枚舉每一層是否直接切掉

　　剩下沒有切的層已經是一個二維的情況了，可以直接用二分圖跑

　　ps：我抄借鑒代碼的時候有很多細節問題不明白，比如二分圖為什么可以不用拆成左右兩邊的點，可以在一排點里直接連。后來發現是因為右邊的點有用的只有它與哪個左部點匹配，所以只需要一排點也可以記錄這些信息（因為我二分圖根本沒學過所以理解起來很吃力……以前都是直接用網絡流跑的從來沒去了解過匈牙利……）

1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 11 inline int read(){ 12 #define num ch-'0' 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch=='-')&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=5005; 22 int head[N],Next[N],ver[N],edge[N],Pre[N],vis[N],tot; 23 int sx[4][N],a,b,c,ans,st[N],num,mn; 24 inline void add(int u,int v){ 25 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 26 } 27 bool dfs(int u){ 28 for(int i=head[u];i;i=Next[i]){ 29 int v=ver[i]; 30 if(!vis[v]){ 31 vis[v]=true; 32 if(!Pre[v]||dfs(Pre[v])){ 33 Pre[v]=u;return true; 34 } 35 } 36 } 37 return false; 38 } 39 void work(int x){ 40 memset(head,0,sizeof(head)); 41 memset(Pre,0,sizeof(Pre)); 42 tot=0; 43 int tmp=0; 44 for(int i=0;i<a;++i){ 45 if(x&(1<<i)) st[i+1]=false,++tmp; 46 else st[i+1]=true; 47 } 48 for(int i=1;i<=num;++i) 49 if(st[sx[1][i]]) add(sx[2][i],sx[3][i]); 50 for(int i=1;i<=b;++i){ 51 for(int j=1;j<=c;++j) vis[j]=false; 52 if(dfs(i)) ++tmp; 53 } 54 cmin(ans,tmp); 55 } 56 int main(){ 57 int T=read(); 58 while(T--){ 59 num=0,ans=inf; 60 a=read(),b=read(),c=read(); 61 mn=min(a,min(b,c)); 62 for(int i=1;i<=a;++i) 63 for(int j=1;j<=b;++j) 64 for(int k=1;k<=c;++k){ 65 int u=read(); 66 if(!u) continue; 67 sx[1][++num]=i; 68 sx[2][num]=j; 69 sx[3][num]=k; 70 } 71 if(mn==b) swap(a,b),swap(sx[1],sx[2]); 72 else if(mn==c) swap(a,c),swap(sx[1],sx[3]); 73 for(int i=0;i<(1<<a);++i) work(i); 74 printf("%d\n",ans); 75 } 76 return 0; 77 }

?

轉載于:https://www.cnblogs.com/bztMinamoto/p/9514404.html

總結

以上是生活随笔為你收集整理的bzoj3140: [Hnoi2013]消毒（二分图）的全部內容，希望文章能夠幫你解決所遇到的問題。

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