bzoj 4554 游戏

Posted on | Views:

最大流.

  • 比较明显是个网络流,考虑如何建模.
  • 硬石头将每一行分成了若干块,每一块内最多放一个炸弹,每一列也同理.然后对每一行/列的块建出它们的点,每一块能通过的流量都是 $1$ .对于空地 $(x,y)$ ,就从 $(x,y)$ 所在的行块向 $(x,y)$ 所在的列块连流量为 $1$ 的边就好了.
  • 再建出源汇点连上这些块,跑一个最大流即可.
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e3+10,MAXM=3e5+10,N=51;
int n,m,Map[N][N],bx[N][N],by[N][N],tx=0,ty=0;
const int inf=1e9;
char buf[N];
struct Edge
{
	int nx,to,flow;
}E[MAXM];
int head[MAXN],ecnt=-1;
void addedge(int u,int v,int flow)
{
	++ecnt;
	E[ecnt].to=v;
	E[ecnt].nx=head[u];
	E[ecnt].flow=flow;
	head[u]=ecnt;
}
void ins(int u,int v,int flow)
{
	addedge(u,v,flow);
	addedge(v,u,0);
}
int trans(char c)
{
	if(c=='*')
		return 0;
	if(c=='x')
		return 1;
	return 2;
}
int cur[MAXN],dis[MAXN],flow[MAXN],dep[MAXN];
queue<int> q;
bool bfs(int S,int T)
{
	for(int i=1;i<=T;++i)
		cur[i]=head[i];
	memset(dep,-1,sizeof dep);
	dep[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=E[i].nx)
		{
			int v=E[i].to;
			if(dep[v]==-1 && E[i].flow)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}		
		}
	}
	return dep[T]!=-1;
}
int dfs(int u,int T,int limit)
{
	if(u==T || !limit)
		return limit;
	int f,Flow=0;
	for(int i=cur[u];i!=-1;i=E[i].nx)
	{
		cur[u]=i;
		int v=E[i].to;
		if(dep[v]==dep[u]+1 && (f=dfs(v,T,min(limit,E[i].flow))))
		{
			Flow+=f;
			limit-=f;
			E[i].flow-=f;
			E[i^1].flow+=f;
			if(!limit)
				break;
		}
	}
	return Flow;
}
int Dinic(int S,int T)
{
	int Maxflow=0;
	while(bfs(S,T))
		Maxflow+=dfs(S,T,inf);
	return Maxflow;
}
void solve()
{
	for(int i=1;i<=n;++i)
	{
		++tx;
		for(int j=1;j<=m;++j)
		{
			bx[i][j]=tx;
			if(Map[i][j]==2)
				++tx;
		}
	}
	for(int j=1;j<=m;++j)
	{
		++ty;
		for(int i=1;i<=n;++i)
		{
			by[i][j]=ty;
			if(Map[i][j]==2)
				++ty;
		}
	}
	int S=tx+ty+1,T=tx+ty+2;
	for(int i=1;i<=tx;++i)
		ins(S,i,1);
	for(int i=1;i<=ty;++i)
		ins(i+tx,T,1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(!Map[i][j])
				ins(bx[i][j],by[i][j]+tx,1);
	cout<<Dinic(S,T)<<endl;
}
int main()
{
	memset(head,-1,sizeof head);
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		scanf("%s",buf+1);
		for(int j=1;j<=m;++j)
			Map[i][j]=trans(buf[j]);
	}
	solve();
	return 0;
}