題目鏈接：點擊查看

題目大意：給出一個n*n的棋盤，我們需要盡可能多地放置1*2大小的方塊，有一些位置是不允許擺放的，問最多能放多少方塊

題目分析：看到1*2大小的方塊，就直接聯想到之前狀壓dp的那個鋪瓷磚的題了，有些不同的是，這個題目多了不允許擺放的點，并且題目數據給的很小，而且最后讓求的還是最多能放多少方塊，而不是方案數，換句話說，這個題用狀態壓縮就不太好做了，我們可以換個思路，因為每個點若想將其用方塊覆蓋，要么就是豎著放一塊，要么就是橫著放一塊，只有這兩種方法，所以這個題目就轉換成了一個二分圖的問題了，但這個題并不是之前那樣關于橫縱坐標求最小路徑覆蓋的問題，不用想的太復雜，我們只需要讓盡可能多的點被覆蓋即可，因為每覆蓋兩個點對答案的貢獻相應就加一，但因為每個格子不能重復擺放，所以建邊就成了一件比較麻煩的事情了

我們可以換個角度思考，當一個點(x,y)想要被一個方塊覆蓋時，只能與相鄰四個方向的格子放置同一個方塊才行，現在重點來了，相鄰的四個方向，與當前點，橫縱坐標之和的奇偶性發生了改變，也就是說對于任意一點來說，與其能夠防止方塊的點的奇偶一定是相反的，這樣一來我們就可以直接根據奇偶拆點了，然后對于奇數點或者偶數點分為兩個集合，建圖后跑一下匈牙利即可，這樣最后跑出來的答案就是正確答案了

這個題目算是奇偶拆點的一個比較簡單的模板題了吧，前兩天做過hdu的那個奇偶拆點的題目感覺還挺神奇的，但現在看來發現就是一種固定的套路，以后再看到類似的題目應該能立馬想到這種方式吧

代碼：

#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=110;const int b[4][2]={0,1,0,-1,1,0,-1,0};int num1[N][N],num2[N][N],cnt1,cnt2;bool can[N][N];bool vis[N*N];int match[N*N];vector<int>node[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; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);while(m--)//標記不可用的點{int x,y;scanf("%d%d",&x,&y);can[x][y]=true;} for(int i=1;i<=n;i++)//奇偶拆點for(int j=1;j<=n;j++){if((i+j)&1)num1[i][j]=++cnt1;elsenum2[i][j]=++cnt2;}for(int x=1;x<=n;x++)//建邊for(int y=1;y<=n;y++){if(can[x][y])continue;for(int k=0;k<4;k++){int xx=x+b[k][0];int yy=y+b[k][1];if(xx<=0||yy<=0||xx>n||yy>n)continue;if(can[xx][yy])continue;if((x+y)&1)node[num1[x][y]].push_back(num2[xx][yy]);elsenode[num1[xx][yy]].push_back(num2[x][y]);} }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; }

?

總結

以上是生活随笔為你收集整理的CH - 6801 棋盘覆盖(二分图最大匹配+奇偶拆点)的全部內容，希望文章能夠幫你解決所遇到的問題。

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