这道题其实不难。。。就是建图恶心了点。。。。emm。。。
题意：
多源多汇 + 拆边
青蛙跳柱子， 每根柱子都有一定的承载能力， 青蛙跳上去之后柱子的承载能力就会减一，跳到边界就能活 跳不到就over了，青蛙有一个最大的跳跃距离dis， 把每根柱子拆成两个点， 中间连一条边，为柱子的承载能力， 每个青蛙的初始位置都为一个源 边界为汇 ， 建立超级源s和超级汇t ， s连接所有青蛙的起点，权值为1， 边界和 距离青蛙起点小于dis的点连接t， 权值为INF， 并且建立u->u' u'->v 的边
看完题想建图的时候觉得暴力建图肯定会超时，然后实在想不出什么好的建图方法， 然后暴力建图， emm。。。竟然没超时。。。 还有注意output的英语语法！！！
Dinic + 弧优化：。。。。现在只会写这个了。。。
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define maxn 1000000
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int INF = 0x3f3f3f3f;
int head[maxn], d[maxn], cur[maxn];
int n, m, s, t, dis;
int cnt = ;
struct node{
int u, v, c, next;
}Node[maxn*]; void add_(int u, int v, int c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].c = c;
Node[cnt].next = head[u];
head[u] = cnt++;
} void add(int u, int v, int c)
{
add_(u,v,c);
add_(v,u,);
} bool bfs()
{
queue<int> Q;
mem(d,);
d[s] = ;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i=head[u]; i!=-; i=Node[i].next)
{
node e = Node[i];
if(!d[e.v] && e.c > )
{
d[e.v] = d[e.u] + ;
Q.push(e.v);
if(e.v == t) return ;
}
}
}
return d[t] != ;
} int dfs(int u, int cap)
{
if(u == t || cap == )
return cap;
int ret = ;
for(int &i=cur[u]; i!=-; i=Node[i].next)
{
node e = Node[i];
if(d[e.v] == d[u] + && e.c > )
{
int V = dfs(e.v, min(cap, e.c));
Node[i].c -= V;
Node[i^].c += V;
ret += V;
cap -= V;
if(cap == ) break;
}
}
return ret;
} int Dinic()
{
int ans = ;
while(bfs())
{
memcpy(cur, head, sizeof(head));
ans += dfs(s, INF);
}
return ans;
} int main()
{
char str[][], map[maxn];
int bz[][];
int T, kase = ;
scanf("%d",&T);
while(T--)
{
cnt = ;
int ret = ;
mem(bz,);
mem(head,-);
int ans = ;
scanf("%d%d",&n,&dis);
for(int i=; i<n; i++)
scanf("%s",&str[i]);
for(int i=; i<n; i++)
{
int len = strlen(str[i]);
if( i == ) s = , t = * len * n + ;
for(int j=; j<len; j++)
{
ans++;
int temp = str[i][j] - '';
if(temp != )
{
add(ans, n*len + ans, temp);
if(i-dis < || i+dis >=n || j-dis < || j+dis >= len){
add(n*len+ans, t, INF);
}
for(int k=-dis; k<=dis; k++)
{
for(int g=-dis; g<=dis; g++)
{
int nx = i + k;
int ny = j + g;
if(nx == i && ny == j) continue;
if(nx < || nx >= n || ny < || ny >= len || str[i][j] == '' || abs(i-nx) + abs(j-ny) > dis)
continue;
add(n*len+ans, nx*len+ny+, INF);
// add(n*len+bz[nx][ny], ans, INF);
}
}
}
}
}
for(int i=; i<n; i++)
{
scanf("%s",map);
for(int j=; j<strlen(map); j++)
{
if(map[j] == 'L')
{
ret++;
add(s, i*strlen(map)+j+, );
}
}
}
// for(int i=0; i<cnt; i++)
// cout<< Node[i].u << " " << Node[i].v << " " <<Node[i].c<<endl; int op = ret - Dinic();
// for(int i=0; i<cnt; i++)
// cout<< Node[i].u << " " << Node[i].v << " " <<Node[i].c<<endl; if(op > )
printf("Case #%d: %d lizards were left behind.\n",++kase,op);
else if(op == )
printf("Case #%d: no lizard was left behind.\n",++kase);
else if(op == )
printf("Case #%d: 1 lizard was left behind.\n",++kase); }
return ;
}