題目鏈接

---

題意很簡單，是二分匹配的一種常見的題型，問題就在于怎樣轉換到二分圖上來。

首先對對n*m-k正常點進行編號，然后遍歷查找每一個正常點的上下左右是否能連接（就是判斷另個點是否也是正常的），如果是就在兩者之間建立雙向邊.這樣一個就變成了一個裸的二分匹配了，對n*m-cnt個點跑匈牙利算法，因為加的是雙向邊，所以二分匹配的結果是答案的兩倍，就是判斷結果是否與n*m-k相等即可。

坑點：巨惡心的輸入x表示列，y表示行。

還有32*32=1024? 直接開了1000的數組瘋狂wa，哈哈。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2]= {0,-1,-1,0,0,1,1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=2005;
int a[40][40];
int head[maxn],used[maxn],girl[maxn];
int n,m,sign,cnt;
struct node
{int to,p;
}edge[maxn*10];
void add(int u,int v)
{edge[sign]=node{v,head[u]};head[u]=sign++;
}
void init()
{sign=cnt=0;memset(a,0,sizeof(a));memset(head,-1,sizeof(head));
}
bool check(int x,int y)
{if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!=-1) return true;return false;
}
bool find(int u)
{for(int i=head[u];~i;i=edge[i].p){int v=edge[i].to;if(!used[v]){used[v]=1;if(girl[v]==-1||find(girl[v])){girl[v]=u;return true;}}}return false;
}
int hungry()
{int ans=0;memset(girl,-1,sizeof(girl));for(int i=1;i<=cnt;i++){memset(used,0,sizeof(used));if(find(i)) ans++;}
//    cout<<ans/2<<endl;return ans/2;
}
int main()
{int k,x,y;while(cin>>n>>m>>k){init();for(int i=1;i<=k;i++)scanf("%d %d",&x,&y),a[y][x]=-1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]==0) a[i][j]=++cnt;if(cnt%2!=0) puts("NO");else{for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]!=-1){for(int p=0;p<4;p++){int xx=i+dir[p][0];int yy=j+dir[p][1];if(check(xx,yy))add(a[i][j],a[xx][yy]),add(a[xx][yy],a[i][j]);}}}if(hungry()==cnt/2) puts("YES");else puts("NO");}}return 0;
}

?

總結

以上是生活随笔為你收集整理的POJ - 2446 Chessboard 二分匹配+建图的全部內容，希望文章能夠幫你解決所遇到的問題。

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