BZOJ4554 [HEOI2016 & TJOI2016]游戏

题意

在2016年,佳缘姐姐喜欢上了一款游戏,叫做泡泡堂。简单的说,这个游戏就是在一张地图上放上若干个炸弹,看是否能炸到对手,或者躲开对手的炸弹。在玩游戏的过程中,小H想到了这样一个问题:当给定一张地图,在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列,炸弹的威力可以穿透软石头,但是不能穿透硬石头。给定一张$n \times m$的网格地图:其中*代表空地,炸弹的威力可以穿透,可以在空地上放置一枚炸弹。$x$代表软石头,炸弹的威力可以穿透,不能在此放置炸弹。#代表硬石头,炸弹的威力是不能穿透的,不能在此放置炸弹。例如:给出$1 \times 4$的网格地图*xx*,这个地图上最多只能放置一个炸弹。给出另一个$1 \times 4$的网格地图*x#*,这个地图最多能放置两个炸弹。现在小H任意给出一张$n \times m$的网格地图,问你最多能放置多少炸弹。

题解

考虑对于每一个不可穿透的行或列看做一个点,那么就可以发现可以直接用二分图匹配了,然后网络流就可以了……建边并不复杂,就不多说了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const double eps=1e-9;
const int maxn=50+10;
const int maxnode=1300;
const int maxe=1e5+10;
int map[maxn][maxn],ida[maxn][maxn],idb[maxn][maxn],vis[maxn][maxn];
int to[maxe],nex[maxe],beg[maxe],w[maxe],gap[maxnode],dis[maxnode];
int G[maxnode][maxnode],flaga[maxnode],flagb[maxnode];
int e=1,cnt=0;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void add(int x,int y,int z){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
w[e]=z;
}
int Isap(int x,int f){
if(x==cnt+2)return f;
int res=f,i;
for(i=beg[x];i;i=nex[i]){
if(w[i]>0 && dis[x]==dis[to[i]]+1){
int minflow=Isap(to[i],min(f,w[i]));
w[i]-=minflow;
w[i^1]+=minflow;
res-=minflow;
if(!res)return f;
}
}
if(!(--gap[dis[x]]))dis[cnt+1]=cnt+2;
gap[++dis[x]]++;
return f-res;
}
int main(){
int i,j,k,m,n;
#ifndef ONLINE_JUDGE
freopen("P2825.in","r",stdin);
freopen("P2825.out","w",stdout);
#endif
n=read();m=read();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
char ch=getchar();
while(ch!='#' && ch!='*' && ch!='x')ch=getchar();
if(ch=='x')map[i][j]=1;
if(ch=='#')map[i][j]=2;
}
int cnt1=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if(vis[i][j] || map[i][j]==2)continue;
int pos=j;cnt1++;
while(map[i][pos]<=1 && pos<=m)vis[i][pos]=1,ida[i][pos]=cnt1,pos++;
}
memset(vis,0,sizeof(vis));
int cnt2=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if(vis[i][j] || map[i][j]==2)continue;
int pos=i;cnt2++;
while(map[pos][j]<=1 && pos<=n)vis[pos][j]=1,idb[pos][j]=cnt2,pos++;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j]==0)flaga[ida[i][j]]=flagb[idb[i][j]]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if(map[i][j])continue;
G[ida[i][j]][idb[i][j]]=1;
}
for(i=1;i<=cnt1;i++)
for(j=1;j<=cnt2;j++)
if(G[i][j])add(i,j+cnt1,1),add(j+cnt1,i,0);
cnt=cnt1+cnt2;
for(i=1;i<=cnt1;i++)
if(flaga[i])add(cnt+1,i,1),add(i,cnt+1,0);
for(i=1;i<=cnt2;i++)
if(flagb[i])add(i+cnt1,cnt+2,1),add(cnt+2,i+cnt1,0);
int ans=0;
for(gap[0]=cnt+2;dis[cnt+1]<cnt+2;)ans+=Isap(cnt+1,INF);
printf("%d\n",ans);
return 0;
}