题目大意：
在一个网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高 度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同 一个石柱上。
这个应该还算是比较难的网络流的题目了吧， 至少对我这个刚刚接触新手的人来说只这样的，AC的过程是痛苦而又备受煎熬的，最后一步步调试下来成功提交的那刹那，感觉全身满满的正能量，闲话少扯了，下面开始直接讲我的思路。
一开始是从学长将网络流的ppt里面看到这题的，只知道是个最大流却又不知道怎么建图，然后想了一下，每根石柱上面能够供蜥蜴（包括一开始在它上面的蜥蜴）不会超过石柱的高
度，也就是可以把它的高度作为一个限制，这样把每一根石柱（i，j）（一维化表示为f = i*m+j)拆分为两个点u，v ，其中u= 2*f， v = 2*f+1，（也就是2*f^1),然后建立一条从
u--->v的边，容量为石柱高度。
然后怎样表示各个石柱之间的到达关系呢？对于两根距离不超过d的石柱，也就是蜥蜴能够从一根跳到另一根的时候，例如石柱1,2，可以建立v1--->u2,的一条容量无限大的边，由于
可*跳动，因此应该反向再建一条，即u2-->v1的边。 对于一开始上面就有蜥蜴的石柱，以及能够跳出边界的石柱，我是这样处理的：有蜥蜴的边，从起点s建立一条到该石柱
的拆分点u的边，容量为1，应该是单向的；然后对于能够跳出边界，即到达安全区域的石柱，建立一条从该石柱的拆分点v到汇点t的无穷容量的边。
然后利用ISPA算方法就可以了，初始可分配流量可以大胆的分配为inf，因为起点到每一个石柱（有蜥蜴）拆分点的容量限制为1，这样就可以表示该石柱上一开始有唯一的蜥蜴。
代码如下：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#define esp 1e-6
#define inf 0x0f0f0f0f
#define INF 200000
#define N 30
using namespace std; struct EDGE
{
int i, c;
EDGE *next, *ani;
} *Edge[INF], E[INF];
int Dfn[INF], Now[INF], cnt, flag[INF];
int src, sink;
int n, m, d, tot, ndot;
char aMat[N][N], bMat[N][N]; int dblcmp(double x)
{
if(fabs(x) < esp)
return ;
return x > ? : -;
}//读图
void ReadMat(int r, int &len, char (*Mat)[N])
{
for(int i = ; i < r; i++)
scanf("%s", Mat[i]);
len = strlen(Mat[]);
}//返回石柱的高度
int f(int i, int j)
{
return aMat[i][j] - '';
}//计算两根石柱之间的距离
double cal(double x, double y)
{
return sqrt(x*x+y*y);
}
void add(int i, int j, int c, EDGE &e1, EDGE &e2)
{
e1.i = j, e1.c = c, e1.next = Edge[i], e1.ani = &e2, Edge[i] = &e1;
e2.i = i, e2.c = , e2.next = Edge[j], e2.ani = &e1, Edge[j] = &e2;
}
void build(void)
{
for(int i = ; i < n; i++)
for(int j = ; j < m; j++)
{
int u, v, c;
if((c = f(i, j)))//表示该位置为石柱
{//拆分点
u = *(i*m+j), v = u ^ ;
//拆分点之间建立边
add(u, v, c, E[cnt], E[cnt + ]);
cnt +=;
add(v, u, c, E[cnt], E[cnt + ]);
cnt += ;
if(bMat[i][j] == 'L')//石柱上面有蜥蜴
{
tot++;
add(src, u, , E[cnt], E[cnt + ]);//将源点和该有蜥蜴的石柱连接一条容量为1的边
cnt +=;
}//搜索周围能够到达的石柱
for(int ii = i - d; ii <= i + d; ii++)
for(int jj = j - d; jj <= j + d; jj++)
if(!(ii == i && jj == j))
{
double dist = cal(ii - i, jj -j);
if(dblcmp(d - dist) >= )
{//石柱能够到达边界
if((ii < || ii >= n || jj < || jj >= m ) )
{
if(!flag[v])
add(v, sink, inf, E[cnt], E[cnt + ]),
flag[v] = ,
cnt += ;
}//能够到达另一个石柱
else if(f(ii, jj))
{
u = *(ii*m+jj);//两根石柱之间建立一条无穷容量的边
add(v, u, inf, E[cnt], E[cnt + ]);
cnt += ;
}
}
}
}
}
}
void init(void)
{
memset(Edge, , sizeof(Edge));
memset(flag, , sizeof(flag));
cnt = tot = ;
} int ISAP(int s, int end, int flow)
{
if(s == end)
return flow;
int i, tab = ndot -, now = , vary;
for(EDGE *p = Edge[s]; p && flow - now; p = p->next)
if(p->c)
{
if(Dfn[s] == Dfn[i = p->i] + )
vary = ISAP(i, end, min(flow - now, p->c)),
p->c -= vary, p->ani->c += vary, now +=vary;
if(p->c)
tab = min(tab, Dfn[i]);
if(Dfn[src] == ndot)
return now;
}
if(now == )
{
if(--Now[Dfn[s]] == )
Dfn[src] = ndot;
Now[Dfn[s] = tab + ]++;
}
return now;
}
int max_flow(int s, int end)
{
memset(Dfn, , sizeof(Dfn));
memset(Now, , sizeof(Now));
Now[] = ndot;
int ret = ;
for(; Dfn[s] < ndot;)
{ ret += ISAP(s, end, inf);
}
return ret;
}
int main(void)
{
int T;
for(int t = scanf("%d", &T); t <= T; t++)
{
init();
scanf("%d%d", &n, &d);
ReadMat(n, m, aMat);
ReadMat(n, m, bMat);
src = *n*m, sink = *n*m+;
build();
ndot = sink + ;
int ans = max_flow(src, sink);
ans = tot - ans;
if(ans)
printf("Case #%d: %d lizard%sleft behind.\n", t,ans,(ans == )?" was ":"s were ");
else printf("Case #%d: no lizard was left behind.\n", t);
}
return ;
}