蜥蜴
【问题描述】
在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。
【输入格式】
输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。
【输出格式】
输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。
【样例输入】
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
【样例输出】
1
【数据范围】
100%的数据满足：1<=r, c<=20, 1<=d<=4
题解：
题目中石柱的高度其实就是限制了点的通过次数
那么把每一个点拆成两个点，分别是进入点和离开点
每个进入点向对应的离开点连一条容量为石柱高度的边
每个离开点向能跳到的进入点连一条容量为无限的边
源点向每个有蜥蜴的进入点连一条容量为1的边
每个能跳出边界的离开点向汇点连一条容量为无限的边
跑一遍最大流
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x;
char c;
while((c = getchar()) < '' || c > '');
x = c - '';
while((c = getchar()) >= '' && c <= '') x = x * + c - '';
return x;
}
const int inf = ;
const int me = ;
int r, c, d, n;
int num;
int S, T;
struct shape
{
int x, y;
};
shape pos[me];
int point[][];
int tot = , nex[me], fir[me], to[me], val[me];
inline void Add(const int &x, const int &y, const int &z)
{
nex[++tot] = fir[x];
fir[x] = tot;
to[tot] = y;
val[tot] = z;
}
inline void Ins(const int &x, const int &y, const int &z)
{
Add(x, y, z);
Add(y, x, );
}
inline int Min(const int &x, const int &y)
{
return (x < y) ? x : y;
}
inline int Sqr(const int &x)
{
return x * x;
}
int dep[me], que[me];
inline bool Bfs()
{
int t = , w = ;
memset(dep, -, sizeof(dep));
que[++w] = S;
dep[S] = ;
while(t < w)
{
int u = que[++t];
for(int i = fir[u]; i; i = nex[i])
{
int v = to[i];
if(dep[v] == - && val[i])
{
dep[v] = dep[u] + ;
que[++w] = v;
if(v == T) return true;
}
}
}
return false;
}
int Dinic(const int &u, const int &flow)
{
if(u == T || !flow) return flow;
int wa = ;
for(int i = fir[u]; i; i = nex[i])
{
int v = to[i];
if(dep[v] == dep[u] + && val[i])
{
int go = Dinic(v, Min(flow - wa, val[i]));
if(go)
{
val[i] -= go;
val[i ^ ] += go;
wa += go;
if(wa == flow) break;
}
}
}
return wa;
}
char s[me];
int main()
{
r = Get(), c = Get(), d = Get();
n = r * c;
S = , T = n << | ;
for(int i = ; i <= r; ++i)
{
scanf("%s", s);
for(int j = ; j <= c; ++j)
{
int sa = s[j - ] - '';
if(sa)
{
point[i][j] = ++num;
pos[num] = (shape) {i, j};
Ins(num, num + n, sa);
int dis = Min(i, Min(j, Min(r - i + , c - j + )));
if(dis <= d) Ins(num + n, T, inf);
for(int k = ; k < num; ++k)
{
int x = pos[k].x, y = pos[k].y;
double dist = sqrt(Sqr(x - i) + Sqr(y - j));
if(dist <= d)
{
Ins(point[x][y] + n, num, inf);
Ins(num + n, point[x][y], inf);
}
}
}
}
}
int ans = ;
for(int i = ; i <= r; ++i)
{
scanf("%s", s);
for(int j = ; j <= c; ++j)
if(s[j - ] == 'L')
{
++ans;
Ins(S, point[i][j], );
}
}
while(Bfs()) ans -= Dinic(S, inf);
printf("%d", ans);
}