http://poj.org/problem?id=3020
题意：给你一张由 * 和 o 组成的图，每次可以选取相邻的两个或一个 * ，问最少几次可以把所有的 * 取完。
因为每次只能取相邻的两个，所以可以建出一个二分图，这样问题就变成了二分图的最小路径覆盖问题，而最小路径覆盖数=节点数-最大匹配数，而这里建的是双向边，所以最大匹配数是匈牙利算法跑出来的结果除以二。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int pr[10010];
int n,m,T;
bool vis[10010],map[1010][1010];
char mp[100][100];
bool find(int x)
{for(int i=1;i<=n*m;i++){if(map[x][i]&&!vis[i]){vis[i]=1;if(pr[i]==-1||find(pr[i])){pr[i]=x;return 1;}}}return 0;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);int sum=0,num=0;memset(map,0,sizeof(map));memset(pr,-1,sizeof(pr));memset(mp,0,sizeof(mp));for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mp[i][j]=='*'){num++;if(mp[i-1][j]=='*') map[(i-1)*m+j][(i-2)*m+j]=1;if(mp[i][j-1]=='*') map[(i-1)*m+j][(i-1)*m+j-1]=1;if(mp[i+1][j]=='*') map[(i-1)*m+j][i*m+j]=1;if(mp[i][j+1]=='*') map[(i-1)*m+j][(i-1)*m+j+1]=1;}}}for(int i=1;i<=n*m;i++){memset(vis,0,sizeof(vis));if(find(i)) sum++;}printf("%d\n",(2*num-sum)/2);}return 0;
}