题意：
给一个n*m的棋盘，上面有k个点被挖掉，问是否能用1*2的片段把剩下的棋盘恰好完全覆盖。
思路：
把剩下的顶点编号，若两个顶点可以被一个片段覆盖则他们之间有一条边，则转化为求二分图的最大匹配问题，若匹配数M+k==n*m则可以完全覆盖，否则不行。
代码：
poj 2446 by sepNINE
#include<iostream>
using namespace std;
int chessboard[36][36];
const int maxN=1200;
bool g[maxN][maxN];
bool vis[maxN];
int link[maxN];
int dirr[4]={0,0,-1,1};
int dirc[4]={-1,1,0,0};
int v1,v2,M;bool dfs(int x)
{for(int y=1;y<=v2;++y) if(g[x][y]&&!vis[y]){vis[y]=true;if(link[y]==0||dfs(link[y])){link[y]=x;return true;}}return false;
}void hungary()
{for(int x=1;x<=v1;++x){memset(vis,false,sizeof(vis));if(dfs(x))++M;} return ;
}int main()
{int i,j,n,m,k,cnt;scanf("%d%d%d",&n,&m,&k);memset(chessboard,0,sizeof(chessboard));memset(g,false,sizeof(g));memset(link,0,sizeof(link));int x,y;for(i=0;i<k;++i){scanf("%d%d",&x,&y);chessboard[y][x]=-1;}cnt=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(chessboard[i][j]!=-1)chessboard[i][j]=++cnt;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(chessboard[i][j]>0)for(int p=0;p<4;++p){int newi=i+dirr[p];int newj=j+dirc[p];if(newi>=1&&newi<=n&&newj>=1&&newj<=m&&chessboard[newi][newj]>0){g[ chessboard[i][j] ][ chessboard[newi][newj] ]=1;g[ chessboard[newi][newj] ][ chessboard[i][j] ]=1;}}v1=v2=cnt;M=0;hungary();if(M+k==n*m) printf("YES");elseprintf("NO"); return 0;
}