題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)n*m的地圖，地圖中‘*’代表泥地，‘.’代表空地，現(xiàn)在我們有兩種木板，一種可以覆蓋一行中的任意長度，我們成為行木板，另一種可以覆蓋一列中的任意長度，我們成為列木板，但這兩種木板都不能覆蓋空地，現(xiàn)在要求用最少的木板覆蓋所有泥地

題目分析：因?yàn)槊恳粋€(gè)方格都有兩種方案被覆蓋，即一種是被行木板覆蓋，一種是被行木板所覆蓋，一種是被列木板所覆蓋，這樣一來我們就可以將行木板劃分為一個(gè)集合，列木板劃分為另一個(gè)集合，然后就變成二分圖的匹配問題了，具體該怎么匹配呢，對(duì)于每一個(gè)點(diǎn)(x,y)，我們將該點(diǎn)所對(duì)應(yīng)的行木板和列木板建邊，因?yàn)槲覀円米钌俚倪吀采w掉所有的頂點(diǎn)，這樣問題就轉(zhuǎn)換成了最小點(diǎn)覆蓋的問題了，最小點(diǎn)覆蓋=二分圖最大匹配，跑一遍匈牙利答案就出來了

這個(gè)題的難點(diǎn)我感覺還是在建邊上，只要邊建好了剩下的就是模板題了，這里我是用while來建邊的，感覺不是想象中的那么困難

還有一個(gè)細(xì)節(jié)，就是行泥濘塊和列泥濘塊大概最多能有N*N/2個(gè)，如果按照常規(guī)的匈牙利時(shí)間復(fù)雜度是n*n的，每一次的時(shí)間復(fù)雜度大概到了1e6，如果怕這個(gè)題目會(huì)故意卡時(shí)間，可以選擇用鄰接表存邊，這樣時(shí)間復(fù)雜度就下降到了n*m了

代碼：

#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;char s[N][N];int num1[N][N],num2[N][N];int r[N*N],c[N*N];int cnt1,cnt2;vector<int>node[N*N];bool vis[N*N];int match[N*N];bool dfs(int x) {for(int i=0;i<node[x].size();i++){int y=node[x][i];if(!vis[y]){vis[y]=true;if(!match[y]||dfs(match[y])){match[y]=x;return true;}}}return false; }void init() {for(int i=0;i<N*N;i++)node[i].clear();cnt1=cnt2=0;memset(match,0,sizeof(match));memset(num1,0,sizeof(num1));memset(num2,0,sizeof(num2)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0;i<n;i++)scanf("%s",s[i]);for(int i=0;i<n;i++)//行泥濘塊 for(int j=0;j<m;j++){if(s[i][j]=='*'){num1[i][j]=++cnt1;while(j+1<m&&s[i][j]=='*'&&s[i][j]==s[i][j+1]){num1[i][j+1]=cnt1;j++;}}}for(int j=0;j<m;j++)//列泥濘塊 for(int i=0;i<n;i++){if(s[i][j]=='*'){num2[i][j]=++cnt2;while(i+1<n&&s[i][j]=='*'&&s[i][j]==s[i+1][j]){num2[i+1][j]=cnt2;i++;}}}for(int i=0;i<n;i++)//建邊f(xié)or(int j=0;j<m;j++)if(s[i][j]=='*')node[num1[i][j]].push_back(num2[i][j]);int ans=0;for(int i=1;i<=cnt1;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d\n",ans);}return 0; }

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的POJ - 2226 Muddy Fields(最小点覆盖-二分图最大匹配)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。