题目地址：http://poj.org/problem?id=2226
这个题瞬间感觉智商被爆啊。。这建图方法实在是巧妙。想了将近一个小时也没想出来。无奈看的题解。。又学习了一种建图方法，题目还不错。这题目刚上来就感觉是按行与列分配，写完了答案正确。。然后提交WA。。这才发现这没有那么简单。。还有一个限制条件。。。sad。。这题的建图方法是先按行排列，根据题目的案例，形式如下：
再按列排列，如下：
然后对每一个*的地方把按行与按列排列的连成一条边，最后进行匹配。比如对于第二行第三列的*来说，就相当于map[3][4]=1来连接。原因是，对于每个*来说，只有两种方式可以覆盖它，即按行排列的与按列排列的，所以应当按这两种方式进行二分。代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
int mp[2000][2000], vis[2000], link[2000], mp1[2000][2000], mp2[2000][2000], mpp[2000][2000], k1, k2;
int dfs(int a)
{
int i;
for(i=1;i<=k2;i++)
{
if(!vis[i]&&mp[a][i])
{
vis[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=a;
return 1;
}
}
}
return 0;
}
void hungary()
{
int i, ans=0;
memset(link,-1,sizeof(link));
for(i=1;i<=k1;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
printf("%d\n",ans);
}
int main()
{
int i, j, n, m;
char s[100];
memset(mp,0,sizeof(mp));
scanf("%d%d",&n,&m);
k1=0;
for(i=0;i<n;i++)
{
scanf("%s",s);
for(j=0;j<m;j++)
{
if(s[j]=='*')
{
mpp[i][j]=1;
}
else
mpp[i][j]=0;
}
}
memset(mp1,0,sizeof(mp1));
memset(mp2,0,sizeof(mp2));
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mpp[i][j]==0)
continue ;
if(j==0||(mpp[i][j-1]==0&&mpp[i][j]))
{
mp1[i][j]=++k1;
}
if(mpp[i][j-1]&&mpp[i][j])
{
mp1[i][j]=k1;
}
}
}
k2=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(mpp[j][i]==0)
continue ;
if(j==0||(mpp[j-1][i]==0&&mpp[j][i]))
{
mp2[j][i]=++k2;
}
if(mpp[j-1][i]&&mpp[j][i])
{
mp2[j][i]=k2;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mp1[i][j])
{
mp[mp1[i][j]][mp2[i][j]]=1;
}
}
}
hungary();
return 0;
}