文章目錄

• 題目描述
• 解析
• 代碼

題目描述

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

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

現在請你告訴他，最少要用多少單位的 F 試劑。

解析

非暴力，不合作

首先可以有一個結論：**每次使$min(x,y,z)=1$,一定是不劣的
所以我們就每次一面一面的涂
看一個《弱化版》的題目

在一$N?N$個 的矩陣中，有 $K$個格子中有雜物，現在你有一種能力，一次可以消除一行或一列格子中的雜物，問你至少需要幾次可以將這些雜物全部消完。

這題應該是二分圖的入門題了，把每個點的x坐標與y坐標相連，跑二分圖最大匹配即可
不難發現，消毒這題應該就是消除雜物的升級版，從二維變成了三維
然鵝很快我們就發現并不能推廣到k維。。。
當然如果您能發明三分圖匹配本題就和喝水一樣
那么我們怎么辦呢？
然后就點開了題解
還是暴力的思想了
考慮到數據范圍：
$$a?b?c<=5000$$

那么a、b、c中的最小值應該不超過17
所以我們考慮暴力枚舉最小的一維的選取狀態，然后每次跑一遍匈牙利取答案最小值即可

另外本題還有一個很巧妙的實現技巧
先把坐標存到三個一維數組里
把最小的一維swap到a的位置同時把對應的那一位的數組swap到第一位
代碼實現就變得很簡單了

代碼

#include<bits/stdc++.h> using namespace std; const int N=5020; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,l; struct node{int from,to,nxt; }p[N]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){x,y,fi[x]};fi[x]=cnt; } int vis[N],mat[N]; bool dfs(int x,int tim){if(vis[x]==tim) return false;vis[x]=tim;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]=x;return true;}}return false; } int a,b,c; int hungary(){int res=0;memset(vis,0,sizeof(vis));memset(mat,0,sizeof(mat));for(int i=1;i<=b;i++){if(dfs(i,i)){res++;//printf(" ok:%d\n",i);}}return res; }int q[4][N],num; bool ok[35]; int ans; int calc(){memset(fi,-1,sizeof(fi));cnt=-1;for(int i=1;i<=num;i++){if(ok[q[1][i]]) continue;int x=q[2][i],y=q[3][i];addline(x,y+b);addline(y+b,x);// printf("x=%d y=%d\n",x,y);}return hungary(); } void find(int k,int val){if(k>a){//printf("ok");//printf("-------------val=%d\n",val);//for(int i=1;i<=a;i++) printf("%d ",ok[i]);//printf("\n");ans=min(ans,calc()+val);//printf("---ans=%d\n\n",ans);return;}find(k+1,val);ok[k]=1;find(k+1,val+1);ok[k]=0; } int main(){int T=read();while(T--){a=read();b=read();c=read();num=0;ans=5000;int mn=min(a,min(b,c));for(int i=1;i<=a;i++){for(int j=1;j<=b;j++){for(int k=1;k<=c;k++){int x=read();if(!x) continue;q[1][++num]=i;q[2][num]=j;q[3][num]=k;}}}if(mn==b){swap(a,b);swap(q[1],q[2]);}else if(mn==c){swap(a,c);swap(q[1],q[3]);}find(1,0);printf("%d\n",ans);}return 0; } /**/

總結

以上是生活随笔為你收集整理的YBTOJ洛谷P3231：消毒（二分图匹配）的全部內容，希望文章能夠幫你解決所遇到的問題。

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