【传送门：BZOJ4554】
简要题意：
给出n*m的矩阵，炸弹的炸弹范围是自己所在行和列（如果碰到'#'的话，就会被挡住），可以在'*'点上放炸弹，'#'表示不能放炸弹而且炸弹不能穿透它，'x'表示不能放炸弹但是炸弹可以穿透它，请问放最多炸弹使得每个炸弹都不能炸到其他炸弹
题解：
二分图匹配
因为'#'号会把行列分隔，而且炸弹只能炸掉一个拥有连续的不为'#'块，所以就把分开的所有行和列编号
然后如果有一个炸弹的坐标为x,y，那么就把它所在的行的块的编号连向它所在的列的块的编号
然后最大匹配就可以了
输入这个问题搞了我好久
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; char s[51][51]; struct node { int x,y,next; }a[110000];int len,last[3100]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } char c[4]; struct zuobiao { int x,y; }cc[51][51]; int chw[110000]; int match[110000]; bool findmuniu(int x,int t) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(chw[y]!=t) { chw[y]=t; if(match[y]==0||findmuniu(match[y],t)==true) { match[y]=x; return true; } } } return false; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); len=0;memset(last,0,sizeof(last)); int tx=0;bool bk=false; for(int i=1;i<=n;i++) { bk=false; for(int j=1;j<=m;j++) { if(s[i][j]!='#') { if(bk==false) tx++; cc[i][j].x=tx; bk=true; } else bk=false; } } int ty=0;bk=false; for(int i=1;i<=m;i++) { bk=false; for(int j=1;j<=n;j++) { if(s[j][i]!='#') { if(bk==false) ty++; cc[j][i].y=ty; bk=true; } else bk=false; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j]=='*') ins(cc[i][j].x,cc[i][j].y+tx); memset(chw,0,sizeof(chw)); memset(match,0,sizeof(match)); int ans=0; for(int i=1;i<=tx;i++) if(findmuniu(i,i)==true) ans++; printf("%d ",ans); return 0; }