题目链接：bzoj4554
题目大意：
当给定一张地图，上面有炸弹和石头。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头x，但是不能穿透硬石头#。只能在空地*上放置一枚炸弹。问最多能放多少炸弹。
题解：
匈牙利求二分图最大匹配
这题转化一下就跟bzoj1059差不多。
不能穿透硬石头的话，就把硬石头的另一边当成不同的一行(或列)可以了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 2700
struct node
{
int x,y,next;
}a[maxn*2];int len,first[maxn];
int ask[maxn],tim,bf[maxn];
int x[60][60],y[60][60];char s[60][60];
void ins(int x,int y)
{
++len;a[len].x=x;a[len].y=y;
a[len].next=first[x];first[x]=len;
}
bool ffind(int x)
{
for (int i=first[x];i!=-1;i=a[i].next)
if (ask[a[i].y]!=tim)
{
int y=a[i].y;
ask[y]=tim;
if (bf[y]==-1 || ffind(bf[y]))
{
bf[y]=x;
return true;
}
}
return false;
}
int main()
{
int n,m,num1,num2,ans,i,j,k;
scanf("%d%d",&n,&m);
num1=num2=len=0;
memset(first,-1,sizeof(first));
memset(bf,-1,sizeof(bf));
for (i=1;i<=n;i++)
{
scanf("
");
for (j=1;j<=m;j++) scanf("%c",&s[i][j]);
}
for (i=1;i<=n;i++)
{
num1++;
for (j=1;j<=m;j++)
{
x[i][j]=num1;
if (s[i][j]=='#') num1++;
}
}
for (j=1;j<=m;j++)
{
num2++;
for (i=1;i<=n;i++)
{
y[i][j]=num2;
if (s[i][j]=='#') num2++;
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (s[i][j]=='*') ins(x[i][j],y[i][j]);
tim=ans=0;
memset(ask,0,sizeof(ask));
for (i=1;i<=num1;i++)
{
tim++;
if (ffind(i)) ans++;
}
printf("%d
",ans);
return 0;
}