题解 P2825 【游戏】

题目链接

题目描述中,”#”是可以挡住炸弹爆炸范围的。

那么,我们不妨对地图以”#”来分割地图的横行纵列。

简单来说,就是将地图字符串上横纵以”#”拆分若干子串,然后将每个子串看做一个点。

显然,炸弹只能放置在”*”上面,而一旦放置一个炸弹,必定在其四周无”#”阻挡的串上面不得再放置炸弹。

那么,这就变成了一个二分图匹配的模型了,以源点向每个横行的合法子串连有向边,然后再以每个纵列子串向汇点连有向边。

之后,对于每个横行子串上课可以放置的位置,向每一个纵行子串上面可以放置的位置连有向边。注意是可以放置的位置,子串里面还包括有”x”,这里不能放置炸弹,一定不能连边。

跑网络流,源点到汇点最大流,同时也是二分图最大匹配。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

const int maxn=5010;
const int inf=0x7fffffff;

typedef struct EdgeNode//前向星存边
{
int to,flow;
EdgeNode *next,*turn;
}*Edge;

Edge head[maxn],cur[maxn];
int s,t,n,m,cnt;//cnt为子串编号
int Lv[maxn];
char graph[60][60];//地图
int x[60][60],y[60][60];//用于存储子串的编号

void add(int u,int v,int w)
{
Edge node1=new EdgeNode,node2=new EdgeNode;
node1->to=v,node2->to=u;
node1->flow=w,node2->flow=0;
node1->turn=node2,node2->turn=node1;
node1->next=head[u],node2->next=head[v];
head[u]=node1,head[v]=node2;
}

//以下网络流的板子
bool bfs()
{
queue<int> que;
memset(Lv,-1,sizeof Lv);
que.push(s);
Lv[s]=0;
while(!que.empty())
{
int u=que.front();
que.pop();
for(Edge node=head[u];node;node=node->next)
{
int v=node->to;
if(node->flow&&!~Lv[v])
{
Lv[v]=Lv[u]+1;
que.push(v);
}
}
}
return ~Lv[t];
}

int dfs(int pos,int flow)
{
if(pos==t)
return flow;
int sum=0;
for(Edge node=cur[pos];node;node=node->next)
{
int v=node->to;
if(Lv[v]==Lv[pos]+1&&node->flow)
{
int fl=dfs(v,min(flow-sum,node->flow));
node->flow-=fl,node->turn->flow+=fl,sum+=fl;
if(node->flow)//弧优化
cur[pos]=node;
if(sum==flow)
break;
}
}
return sum;
}

int dinic()
{
int flow=0;
while(bfs())
{
memcpy(cur,head,sizeof(head));
flow+=dfs(s,inf);
}
return flow;
}

int main()
{
scanf("%d%d",&n,&m);
s=0,t=maxn-1;//源点汇点
for(int i=1;i<=n;i++)
scanf("%s",graph[i]+1);
for(int i=1;i<=n;i++)//枚举横行纵列
for(int j=1;j<=m;j++)
if(graph[i][j]!='#')//以"#"分割当然不包括"#"区域
{
if(j==1||graph[i][j-1]=='#')//以"#"分割,并分配一个新的编号给当前子串
add(s,++cnt,1);//源点向横行当前编号子串连边
x[i][j]=cnt;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(graph[j][i]!='#')
{
if(j==1||graph[j-1][i]=='#')//同理
add(++cnt,t,1);//汇点向当前编号的纵行连边
y[j][i]=cnt;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(graph[i][j]=='*')//注意,只有"*"处可以放置炸弹
add(x[i][j],y[i][j],1);
printf("%d\n",dinic());//跑网络流求出二分图最大匹配
return 0;
}