正題

---

大意

一個(gè)n*m的棋盤上有k個(gè)洞，將1*2的木條放在上面，不能鋪在洞上，不能重疊，求能不能鋪滿整個(gè)棋盤。

---

解題思路

用點(diǎn)來(lái)建立二分圖，然后求最大匹配。

但是奇偶建圖會(huì)快兩倍。奇偶建圖就是相鄰的塊可以相連接，所以它們可以不放在同一邊。

---

代碼

#include<cstdio> #include<cstring> #include<iostream> using namespace std; struct line{int to,next; }le[11001]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; int tot,w,s,n,m,k,num[41][41],link[1101],xx,y,one,two,ls[1101]; bool cover[1101],a[41][41]; void add(int x,int y) {le[++tot].next=ls[x];le[tot].to=y;ls[x]=tot; }//鄰接表 bool find(int x)//最大匹配 {int p;for (int q=ls[x];q;q=le[q].next){if (!cover[le[q].to]){cover[le[q].to]=true;p=link[le[q].to];link[le[q].to]=x;if (!p || find(p)) return true;link[le[q].to]=p;}}return false; } int main() {scanf("%d%d%d",&m,&n,&k);w=k;for (int i=1;i<=k;i++){scanf("%d%d",&xx,&y);a[xx][y]=true;}if((n*m-k)&1) return puts("NO")&1;//特判節(jié)省時(shí)間for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (!a[i][j]){if ((i+j)%2==1) num[i][j]=++one;else num[i][j]=++two;//分為奇偶標(biāo)號(hào)}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){if (!a[i][j] && (i+j)%2==1)for (int k=0;k<4;k++){if (i+dx[k]>=1 && i+dx[k]<=n && j+dy[k]>=1 && j+dy[k]<=m)if (!a[i+dx[k]][j+dy[k]])add(num[i][j],num[i+dx[k]][j+dy[k]]);//建立連接}} for (int i=1;i<=one;i++){memset(cover,0,sizeof(cover));if (find(i)) s++;}if (n*m==s*2+w) printf("YES");//計(jì)算答案else printf("NO"); }

總結(jié)

以上是生活随笔為你收集整理的POJ2446-Chessboard【最大匹配,二分图,奇偶建图】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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