題目鏈接：點擊查看

題目大意：給出k塊m*n大小的土地，每塊土地由數字‘0’或26個大寫字母組成，大寫字母代表住戶，數字‘0’代表空地，現在開發商想盡可能多的修建大樓，每個大樓需要占用h*w的面積，而且每塊土地最多只能修一棟大樓，不過住戶不太愿意搬遷，經過協商后，住戶答應在每塊土地上，可以出售掉同一個住戶的所有房屋，不過在其他土地上就不允許再購買該住戶的房屋了，問在此條件下，開發商最多可以建造多少棟大樓

題目分析：題目有點復雜，但理解之后就變得相當簡單了，因為每塊土地開發商都可以選擇買掉任一住戶的所有房屋，以此來增加空地的可用面積，所以每一塊土地可以看做一個頂點，每一個字母（住戶），也可以看做一個頂點，因為每一個住戶只在一塊土地上出售房屋，所以就形成了一個一一對應的關系，簡單來說，就是一個二分圖匹配問題，即以每塊土地來選擇特定的字母，進而達到最大值的一個過程

這樣一來只要建好圖，然后跑一遍匈牙利算法就好了，我感覺難就難在該如何建圖上，一開始實在沒有思路，參考了一下zx學長的代碼之后，就豁然開朗了，我們可以用二維前綴和來判斷，因為題目規定了每個大樓需要占掉h*w面積的土地，并且暗示出這個h*w的面積必須是h*w，而不能是w*h，這樣一來我們只需要在空地或當前字母上，取值為1，否則取值為0，求一下二維前綴和，然后判斷哪一塊h*w大小的區間內的值是h*w即可

這樣建完圖后，還有一個小細節需要注意一下，若某塊土地中，空地的大小已經滿足建大樓的需求，也就是說在當前土地并不需要購買用戶的房屋時，直接讓答案+1即可，剩下的跑一遍匈牙利就好了

現在看zx學長的代碼看多了，代碼風格和學長的風格越來越像了，但水平好像還是不如zx學長的十分之一QAQ

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=55;int k,n,m,h,w;char s[N][N];bool maze[N][N];//maze[k][character]int match[N];int sum[N][N];bool vis[N];bool cal(char ch) {for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='0'||s[i][j]==ch)sum[i][j]=1;elsesum[i][j]=0;sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];if(i>=h&&j>=w&&sum[i][j]-sum[i-h][j]-sum[i][j-w]+sum[i-h][j-w]==h*w)return true;}}return false; }bool dfs(int x) {for(int i=1;i<=26;i++){if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}} return false; }int main() { // freopen("input.txt","r",stdin);int t;cin>>t;while(t--){memset(match,0,sizeof(match));scanf("%d%d%d%d%d",&k,&n,&m,&h,&w);for(int i=1;i<=k;i++){for(int j=1;j<=n;j++)scanf("%s",s[j]+1);for(int j=0;j<=26;j++){char ch=j+'A'-1;maze[i][j]=cal(ch);}}int ans=0;for(int i=1;i<=k;i++){memset(vis,false,sizeof(vis));if(maze[i][0]||dfs(i))ans++;}printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 1358 Housing Complexes(二分图最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

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