BZOJ 1066/洛谷 2472: [SCOI2007]蜥蜴

2018-03-28Chentiancai_nn?

Description

  在一个r行c列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃
到边界外。 每行每列中相邻石柱的距离为1,蜥蜴的跳跃距离是d,即蜥蜴可以跳到平面距离不超过d的任何一个石
柱上。石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减1(如果仍然落在地图内部,则到达的石柱高度不
变),如果该石柱原来高度为1,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个
石柱上。

Input

  输入第一行为三个整数r,c,d,即地图的规模与最大跳跃距离。以下r行为石竹的初始状态,0表示没有石柱
,1~3表示石柱的初始高度。以下r行为蜥蜴位置,“L”表示蜥蜴,“.”表示没有蜥蜴。

Output

  输出仅一行,包含一个整数,即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2  
00000000  
02000000  
00321100  
02000000  
00000000  
........  
........  
..LLLL..  
........  
........

Sample Output

1

HINT

100%的数据满足:1<=r, c<=20, 1<=d<=4

题解

这里的d指的是曼哈顿距离(反正我这么写过了)。
最大流,一个石柱高为k说明这个石柱只能通过k只蜥蜴,拆点,入点向出点连一条流量为k的边。总源点向初始每只有蜥蜴的石柱连一条流量为1的边,每个可以跳出地图的石柱向总汇点连一条inf的边,虽然好像k也可以。

代码

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

const int N = 23,M = 12005,EDGE = 120005,INF = 1e9;
int head[M],nxt[EDGE],to[EDGE],w[EDGE],cnt = -1;
int dep[M],cur[M];
char mp[N][N],mp2[N][N];
int p[N][N],p2[N][N];
int n,m,d,s,t;
int num,nump;
inline void insert(int x,int y,int z){ to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; w[cnt] = z; }
inline bool bfs(){
queue<int> Q; while(!Q.empty()) Q.pop();
memset(dep,0,sizeof dep); dep[s] = 1; Q.push(s);
do{
int x = Q.front(); Q.pop();
for(int i = head[x];i != -1;i = nxt[i])
if(w[i] > 0 && dep[to[i]] == 0){
dep[to[i]] = dep[x]+1;
Q.push(to[i]);
}
}while(!Q.empty());
return dep[t] > 0;
}
inline int dfs(int x,int flow){
if(x == t) return flow;
for(int &i = cur[x];i != -1;i = nxt[i])
if(w[i] > 0 && dep[to[i]] == dep[x]+1){
int di = dfs(to[i],min(flow,w[i]));
if(di > 0){
w[i] -= di; w[i^1] += di;
return di;
}
}
return 0;
}

inline void dinic(){
int ans = 0;
while(bfs()){
for(int i = 0;i <= 2*num+1;++i) cur[i] = head[i];
while(int d = dfs(s,INF)) ans += d;
}
printf("%d",nump-ans);
}

int main(){
n = read(); m = read(); d = read();
for(int i = 1;i <= n;++i){
scanf("%s",mp[i]+1);
for(int j = 1;j <= m;++j) if(mp[i][j] != '0') p[i][j] = ++num;
}
for(int i = 1;i <= n;++i){
scanf("%s",mp2[i]+1);
for(int j = 1;j <= m;++j) if(mp2[i][j] == 'L') nump++;
}
memset(head,-1,sizeof head);
s = 0; t = num*2+1;
for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) if(mp2[i][j] == 'L'){
insert(s,p[i][j],1); insert(p[i][j],s,0);
}
for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) if(mp[i][j] != '0'){
int x = mp[i][j]-'0';
insert(p[i][j],p[i][j]+num,x); insert(p[i][j]+num,p[i][j],0);
for(int I = 1;I <= n;++I) for(int J = 1;J <= m;++J) if(mp[I][J] != '0' && (I != i || J != j)){
if(abs(I-i)+abs(J-j) > d) continue;
insert(p[i][j]+num,p[I][J],INF); insert(p[I][J],p[i][j]+num,0);
}
if(i <= d || j <= d || n-i < d || m-j < d){
insert(p[i][j]+num,t,x); insert(t,p[i][j]+num,0);
}
}
dinic();
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close