题目意思是有一些蜥蜴在一个迷宫里面，求这些蜥蜴还有多少是无论如何都逃不出来的。题目只给定一个行数n，一个最远能够跳跃的距离d。每只蜥蜴有一个初始的位置，题目保证这些位置都有一些柱子，但是它每离开一根柱子，柱子的高度就会降低1m，问最多能有多少只跳不出去。
将每个柱子在的点进行拆点，把每一个点拆完之后连一条容量为所在点柱子高度的边。从原点连一条容量为1的边，然后找到每个可以直接跳出的点，将这些点与汇点 相连容量为无穷。每个柱子与它可以到达的点的容量也为无穷。
4 3 1 1111 1111 1111 LLLL LLLL LLLL 3 2 00000 01110 00000 ..... .LLL. ..... 3 1 00000 01110 00000 ..... .LLL. ..... 5 2 00000000 02000000 00321100 02000000 00000000 ........ ........ ..LLLL.. ........ ........
Case #1: 2 lizards were left behind. Case #2: no lizard was left behind. Case #3: 3 lizards were left behind. Case #4: 1 lizard was left behind.
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)
using namespace std;
const int maxn = 1100;
int cnt;
int n, m;
int cur[maxn], head[maxn];
int dis[maxn], gap[maxn];
int aug[maxn], pre[maxn];
int num[maxn];
struct node
{
int v, w;
int next;
} f[2010000];
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w)
{
f[cnt].v = v;
f[cnt].w = w;
f[cnt].next = head[u];
head[u] = cnt++;
f[cnt].v = u;
f[cnt].w = 0;
f[cnt].next = head[v];
head[v] = cnt++;
}
int SAP(int s, int e, int n)
{
int max_flow = 0, v, u = s;
int id, mindis;
aug[s] = INF;
pre[s] = -1;
memset(dis, 0, sizeof(dis));
memset(gap, 0, sizeof(gap));
gap[0] = n;
for (int i = 0; i <= n; ++i) cur[i] = head[i];/// 初始化当前弧为第一条弧
while (dis[s] < n)
{
bool flag = false;
if (u == e)
{
max_flow += aug[e];
for (v = pre[e]; v != -1; v = pre[v]) /// 路径回溯更新残留网络
{
id = cur[v];
f[id].w -= aug[e];
f[id^1].w += aug[e];
aug[v] -= aug[e]; /// 修改可增广量，以后会用到
if (f[id].w == 0) u = v; /// 不回退到源点，仅回退到容量为0的弧的弧尾
}
}
for (id = cur[u]; id != -1; id = f[id].next)/// 从当前弧开始查找允许弧
{
v = f[id].v;
if (f[id].w > 0 && dis[u] == dis[v] + 1) /// 找到允许弧
{
flag = true;
pre[v] = u;
cur[u] = id;
aug[v] = min(aug[u], f[id].w);
u = v;
break;
}
}
if (flag == false)
{
if (--gap[dis[u]] == 0) break; ///gap优化，层次树出现断层则结束算法
mindis = n;
cur[u] = head[u];
for (id = head[u]; id != -1; id = f[id].next)
{
v = f[id].v;
if (f[id].w > 0 && dis[v] < mindis)
{
mindis = dis[v];
cur[u] = id; /// 修改标号的同时修改当前弧
}
}
dis[u] = mindis + 1;
gap[dis[u]]++;
if (u != s) u = pre[u]; /// 回溯继续寻找允许弧
}
}
return max_flow;
}
char map1[maxn][maxn], map2[maxn][maxn];
int vis[maxn][maxn];
double dist(int x1, int y1, int x2, int y2)
{
double a = x1, b = y1, c = x2, d = y2;
return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
int main()
{
int Case = 1;
int d;
int K;
cin >>K;
while(K--)
{
scanf("%d %d",&n, &d);
init();
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; i++) cin >>map1[i];
for(int j = 0; j < n; j++) cin >>map2[j];
int len = strlen(map1[0]);
int k = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < len; j++) if(map1[i][j]-'0' > 0) vis[i][j] = ++k;
int S = 0;
int T = 2*k+1;
int en = T+1;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < len; j++)
{
if(map1[i][j]-'0' > 0)
{
add(vis[i][j], vis[i][j]+k, map1[i][j]-'0');
for(int ii = 0; ii < n; ii++)
{
for(int jj = 0; jj < len; jj++)
{
if(i == ii && j == jj) continue;
double s = dist(i, j, ii, jj);
if(vis[ii][jj] && (double)d >= s) add(vis[i][j]+k, vis[ii][jj], INF-10);
}
}
}
}
}
int kk = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < len; j++)
{
if(map2[i][j] == 'L')
{
kk++;
add(S, vis[i][j], 1);
}
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < len; j++)
if(map1[i][j]-'0' > 0) if(i+1<=d || j+1<=d || n-i<=d || len-j<=d) add(vis[i][j]+k, T, INF-10);
int ans = SAP(S, T, en);
cout<<"Case #"<<Case++<<": ";
if(kk-ans == 0) cout<<"no lizard was left behind."<<endl;
else if(kk-ans == 1) cout<<"1 lizard was left behind."<<endl;
else cout<<kk-ans<<" lizards were left behind."<<endl;
}
return 0;
}
HDU 2732 Leapin' Lizards(拆点+最大流),布布扣,bubuko.com
HDU 2732 Leapin' Lizards(拆点+最大流)
原文：http://blog.csdn.net/xu12110501127/article/details/38640307