BZOJ 4554 游戏

发表于 | 更新于

Link

比较简单不写题解了 那为什么放上来呢？ 因为有向图网络流反向边容量设成了与正向边相同查了挺长时间。

Code

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
#include "lucida"
using std::fill;
using std::copy;
const int MAXN=50+5,MAXP=5000+11,MAXM=(MAXP<<1)+MAXP,INF=0x1f1f1f1f;
const char BLANK='*',SOFT='x',HARD='#';
struct Edge {
	int to,cap,v;Edge *pre,*rev;
	Edge(int to,int cap,Edge *pre):to(to),cap(cap),v(0),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXM<<1);
		return Me++;
	}
}*G[MAXP];
void Adde(int f,int t,int cap) {
	G[f]=new Edge(t,cap,G[f]);
	G[t]=new Edge(f,0,G[t]);//cap????
	G[f]->rev=G[t];
	G[t]->rev=G[f];
}
namespace isap {
	const int MAXN=MAXP;
	int s,t,n,d[MAXN],num[MAXN];
	Edge *arc[MAXN],*pe[MAXN];
	int Aug() {
		int minf=INF;
		for(Edge *e=pe[t];e;e=pe[e->rev->to]) {
			chkmn(minf,e->cap-e->v);
		}
		for(Edge *e=pe[t];e;e=pe[e->rev->to]) {
			e->v+=minf;
			e->rev->v-=minf;
		}
		return minf;
	}
	bool Advanced(int &cp) {
		for(Edge *&e=arc[cp];e;e=e->pre) {
			if(e->cap>e->v && d[cp]==d[e->to]+1) {
				pe[cp=e->to]=e;
				return 1;
			}
		}
		return 0;
	}
	int ISAP() {
		fill(d+s,d+t+1,0);
		fill(num,num+1+n,0);
		copy(G+s,G+t+1,arc+s);
		num[0]=n;int flow=0;pe[s]=0;
		for(int cp=s;d[s]<n;cp=cp==t?(flow+=Aug(),s):cp) {
			if(!Advanced(cp)) {
				if(!--num[d[cp]]) {
					break;
				}
				d[cp]=n;
				for(Edge *e=(arc[cp]=G[cp]);e;e=e->pre) {
					if(e->cap>e->v) {
						chkmn(d[cp],d[e->to]+1);
					}
				}
				cp=cp==s?cp:pe[cp]->rev->to;
			}
		}
		return flow;
	}
}using isap::ISAP;
int main() {
	freopen("input","r",stdin);
	//先搜出经过每个点的所有横长条和竖长条
	//一个横长条只能配一个竖长条
	static char map[MAXN][MAXN];
	static int xi[MAXN][MAXN],yi[MAXN][MAXN];
	int xic=0,yic=0,n,m;
	is>>n>>m;
	for(int x=1;x<=n;++x) {
		is>>(map[x]+1);//map[x]..
	}
	for(int x=1;x<=n;++x) {
		map[x][0]=map[x][m+1]=HARD;
	}
	for(int y=1;y<=m;++y) {
		map[0][y]=map[n+1][y]=HARD;
	}
	for(int x=1;x<=n;++x) {
		for(int y=1;y<=m;++y) {
			if(map[x][y]==HARD) {
				continue;
			}
			if(!xi[x][y]) {
				++xic;
				for(int k=x;map[k][y]!=HARD;++k) {
					xi[k][y]=xic;
				}
			}
			if(!yi[x][y]) {
				++yic;
				for(int k=y;map[x][k]!=HARD;++k) {
					yi[x][k]=yic;
				}
			}
		}
	}
	isap::s=0;isap::t=xic+yic+1;isap::n=isap::t+1;
	for(int i=1;i<=xic;++i) {
		Adde(isap::s,i,1);
	}
	for(int i=1;i<=yic;++i) {
		Adde(i+xic,isap::t,1);
	}
	for(int x=1;x<=n;++x) {
		for(int y=1;y<=m;++y) {
			if(map[x][y]==BLANK) {
				Adde(xi[x][y],yi[x][y]+xic,1);
			}
		}
	}
	int Ans=ISAP();
	os<<Ans<<'\n';
	return 0;
}