题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3360
题目大意：
在一个n*m的格子中，每个格子有一个数值，-1表示空，其余表示财宝。每个财宝的数值转换成二进制数，
12个二进制位上数值，从右到左，第i个位是1表示图上相应第i序号位置需要有警卫。所有的要求位置有警卫财宝才安全。
财宝可以被警卫替换。问至少需要替换多少财宝才能保证所有财宝的安全。
解题思路：
需要警戒位置是财宝的讯号对财宝位置讯号建边。由于警戒位置与财宝位置的横纵坐标奇偶相反，可以建得二分图。
对于所建图，根据题意就是找出最少的顶点使得剩余顶点覆盖所有的边，即最小顶点覆盖数为答案。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1e2+;
vector<int>v[N*N]; int n,m,xN,yN;
int link[N*N],num[N][N],mp[N][N];
bool vis[N*N];
int dir[][] = {{-,-},{-,-},{-,},{-,},{,},{,},{,-},{,-},{-,},{,},{,},{,-}}; bool dfs(int u){
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!vis[t]){
vis[t]=true;
if(link[t]==-||dfs(link[t])){
link[t]=u;
return true;
}
}
}
return false;
} int max_match(){
memset(link,-,sizeof(link));
int ans=;
for(int i=;i<=xN;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
return ans;
} bool check(int x,int y){
if(x<=||y<=||x>n||y>m||mp[x][y]==-) return false;
return true;
} void init(){
xN=yN=;
for(int i=;i<=n*m;i++) v[i].clear();
} int main(){
int cas=;
while(~scanf("%d%d",&n,&m)&&n&&m){
init();
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if((i+j)%==) num[i][j]=++xN;
else num[i][j]=++yN;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&mp[i][j]);
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]==-) continue;
for(int k=;k<;k++){
if(mp[i][j]&(<<k)){
int x=i+dir[k][];
int y=j+dir[k][];
if(!check(x,y)) continue;
if((i+j)%==) v[num[i][j]].push_back(num[x][y]);
else v[num[x][y]].push_back(num[i][j]);
}
}
}
}
printf("%d. %d\n",++cas,max_match());
}
return ;
}