原题链接：P2825 [HEOI2016/TJOI2016]游戏
题意
就是在一张图上放炸弹，炸弹占领横纵一行一列。
炸弹不能穿透硬石头，软硬石头上都不能放炸弹。
求最多能放几个炸弹。
分析
（第一道没看题解AC的网络流）
感觉跟这道题有点像啊。。
如果没有硬石头的限制，这道题就是要求行和列的匹配。
如果加了硬石头怎么办？
一个位置，它能覆盖到的行应该是往上下一直延伸到硬石头，往左右一直延伸到硬石头。
我们可以把行和列重分块（长或宽为$1$），一个块内只能有空格和软石头，然后就是块和块的匹配了。
一个位置可以匹配它横向和纵向的两个块，我们从横向往纵向连边。
然后源点向所有的横向连边，所有的纵向往汇点连边，跑一遍网络流版二分图匹配就可以了。
代码
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define Mid ((l+r)>>1) 4 #define ull unsigned long long 5 using namespace std; 6 const int N=59,M=1e5+1009; 7 int read(){ 8 char c;int num,f=1; 9 while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0'; 10 while(c=getchar(), isdigit(c))num=num*10+c-'0'; 11 return f*num; 12 } 13 int readc(){ 14 char c=getchar(); 15 while(c!='#'&&c!='*'&&c!='x')c=getchar(); 16 if(c=='#')return 2; 17 if(c=='*')return 1; 18 if(c=='x')return 0; 19 } 20 int n,m,g[N][N],cnt1,cnt2; 21 int L[N][N],R[N][N],dis[M],s,t; 22 int head[M],nxt[M],ver[M],edge[M],tot=1; 23 queue<int>q; 24 void add_edge(int u,int v,int w){ 25 //cout<<u<<" "<<v<<endl; 26 ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;edge[tot]=w; 27 ver[++tot]=u;nxt[tot]=head[v];head[v]=tot;edge[tot]=0; 28 } 29 bool bfs(){ 30 while(q.size())q.pop();q.push(s); 31 memset(dis,0,sizeof(dis));dis[s]=1; 32 while(q.size()){ 33 int x=q.front();q.pop(); 34 for(int i=head[x];i;i=nxt[i]){ 35 if(dis[ver[i]]||!edge[i])continue; 36 dis[ver[i]]=dis[x]+1; 37 q.push(ver[i]); 38 if(ver[i]==t)return 1; 39 } 40 } 41 return 0; 42 } 43 int dinic(int x,int flow){ 44 if(x==t)return flow; 45 int res=flow,y,k; 46 for(int i=head[x];i&&res;i=nxt[i]){ 47 y=ver[i]; 48 if(dis[y]!=dis[x]+1||!edge[i])continue; 49 k=dinic(y,min(res,edge[i])); 50 if(!t)dis[y]=0; 51 edge[i]-=k;edge[i^1]+=k; 52 res-=k; 53 } 54 return flow-res; 55 } 56 int main() 57 { 58 //freopen("4.in","r",stdin); 59 //freopen("data.out","w",stdout); 60 n=read();m=read(); 61 for(int i=1;i<=n;i++) 62 for(int j=1;j<=m;j++) 63 g[i][j]=readc(); 64 for(int i=1;i<=n;i++){ 65 for(int j=1;j<=m;j++){ 66 if(g[i][j]==2||L[i][j])continue; 67 cnt1++; 68 for(int k=j;k<=m&&g[i][k]!=2;k++) 69 L[i][k]=cnt1; 70 } 71 } 72 int t1=cnt1; 73 //编号行 74 /* 75 cout<<endl; 76 for(int i=1;i<=n;i++){ 77 for(int j=1;j<=m;j++) 78 cout<<L[i][j]<<" "; 79 cout<<endl; 80 } 81 cout<<endl; 82 */ 83 for(int j=1;j<=m;j++){ 84 for(int i=1;i<=n;i++){ 85 if(g[i][j]==2||R[i][j])continue; 86 cnt1++; 87 for(int k=i;k<=n&&g[k][j]!=2;k++) 88 R[k][j]=cnt1; 89 } 90 } 91 //编号列 92 /* 93 cout<<endl; 94 for(int i=1;i<=n;i++){ 95 for(int j=1;j<=m;j++) 96 cout<<R[i][j]<<" "; 97 cout<<endl; 98 } 99 cout<<endl; 100 */ 101 //重标号 102 s=cnt1+11;t=cnt1+15; 103 for(int i=1;i<=t1;i++) 104 add_edge(s,i,1); 105 for(int i=t1+1;i<=cnt1;i++) 106 add_edge(i,t,1); 107 for(int i=1;i<=n;i++) 108 for(int j=1;j<=m;j++){ 109 //横号竖向连接 110 if(g[i][j]!=1)continue; 111 //cout<<L[i][j]<<" "<<R[i][j]<<endl; 112 add_edge(L[i][j],R[i][j],1); 113 } 114 //连边 115 /* 116 for(int i=head[7];i;i=nxt[i]) 117 cout<<ver[i]<<" "; 118 cout<<endl; 119 */ 120 int maxflow=0,flow; 121 while(bfs())while(flow=dinic(s,(1<<31)-1))maxflow+=flow; 122 printf("%d ",maxflow); 123 return 0; 124 } 125 /* 126 由于有硬石头和软石头，就不能当做普通的二分图匹配跑了 127 对于一个石头分隔开的一段，我们完全可以把它当成两段匹配 128 可以匹配的行数和列数不一样 129 具体来说，可以按照硬石头的位置，把一段行和一段列拆开，重标号 130 软石头是不能放的 131 所以在连边的时候注意 132 然后跑匹配就可以了。 133 134 */ 135 136 137 138 139 140 141 142 143 144 145 146