题意：题目是说一个n*m的迷宫中，有每个格子有柱子。柱子高度为0~3，高度为0的柱子是不能站的（高度为0就是没有柱子）在一些有柱子的格子上有一些蜥蜴，一次最多跳距离d,相邻格子的距离是1，只要跳出迷宫就是安全的。这个距离是曼哈顿距离（好像是的）。蜥蜴一次最多跳距离d,但是起跳的地方的柱子高度会减一，一个柱子同一时间只能有一个蜥蜴要求最少几个不能逃出迷宫。
链接：点我
看懂了，明天拍
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
#define pb(a) push_back(a)
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt,cnt;
char s1[][],s2[][];
struct Edge
{
int to,next,cap,flow;
}edge[];//注意是MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
int maze[][];
void init()
{
tol = ;
memset(head,-,sizeof(head));
}
//加边，单向图三个参数，双向图四个参数
void addedge(int u,int v,int w,int rw=)
{
edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];
edge[tol].flow = ;head[u] = tol++;
edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v];
edge[tol].flow = ;head[v]=tol++;
}
//输入参数：起点、终点、点的总数
//点的编号没有影响，只要输入点的总数
int sap(int start,int end,int N)
{
memset(gap,,sizeof(gap));
memset(dep,,sizeof(dep));
memcpy(cur,head,sizeof(head));
int u = start;
pre[u] = -;
gap[] = N;
int ans = ;
while(dep[start] < N)
{
if(u == end)
{
int Min = INF;
for(int i = pre[u];i != -; i = pre[edge[i^].to])
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
for(int i = pre[u];i != -; i = pre[edge[i^].to])
{
edge[i].flow += Min;
edge[i^].flow -= Min;
}
u = start;
ans += Min;
continue;
}
bool flag = false;
int v;
for(int i = cur[u]; i != -;i = edge[i].next)
{
v = edge[i].to;
if(edge[i].cap - edge[i].flow && dep[v]+ == dep[u])
{
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if(flag)
{
u = v;
continue;
}
int Min = N;
for(int i = head[u]; i != -;i = edge[i].next)
if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
{
Min = dep[edge[i].to];
cur[u] = i;
}
gap[dep[u]]--;
if(!gap[dep[u]])return ans;
dep[u] = Min+;
gap[dep[u]]++;
if(u != start) u = edge[pre[u]^].to;
}
return ans;
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d",&tt);
int ca=;
int d;
while(tt--)
{
ca++;
init();
scanf("%d%d",&n,&d);
for(i=;i<n;i++)
{
scanf("%s",&s1[i]);
}
m=strlen(s1[]);
int tot=;
cl(maze);
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
if(s1[i][j]>'') //说明改点可跳
{
maze[i][j]=++tot;
addedge(*tot-,*tot,s1[i][j]-'');
}
}
} //这里的tot要注意，如果一开始是tot++，那么比实际会多出一个点
int start=,end=*tot+,nodenum=*tot+;
int sum=;
for(i=;i<n;i++)
{
scanf("%s",s2[i]);
for(j=;j<m;j++)
{
if(s2[i][j]=='L')
{
sum++;
addedge(start,*maze[i][j]-,);
}
}
}
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
if(maze[i][j]) //能直接跳出边界的点连上汇点
{
for(int x=-d;x<=d;x++)
{
for(int y=fabs(x)-d;y<=d-fabs(x);y++) //新技能get
{
int ni=i+x;
int nj=j+y;
if(ni<||ni>=n||nj<||nj>=m)continue;
if(ni==i&&nj==j) continue;
if(maze[ni][nj]==) continue;
addedge(*maze[i][j],*maze[ni][nj]-,INF); //这里的跳跃是无限流的
}
}
if(i<d||j<d||n-i<=d||m-j<=d) addedge(*maze[i][j],end,INF);
}
}
}
int ans=sum-sap(start,end,nodenum);
if(ans==)printf("Case #%d: no lizard was left behind.\n",ca);
else if(ans==)printf("Case #%d: 1 lizard was left behind.\n",ca);
else printf("Case #%d: %d lizards were left behind.\n",ca,ans);
}
}
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std; const int MAXN=;
const int MAXM=;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,cap;
}edge[MAXM];//注意是MAXM
int tol;
int head[MAXN];
int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN]; void init()
{
tol=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w,int rw=)
{
edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++;
edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];head[v]=tol++;
}
int sap(int start,int end,int nodenum)
{
memset(dis,,sizeof(dis));
memset(gap,,sizeof(gap));
memcpy(cur,head,sizeof(head));
int u=pre[start]=start,maxflow=,aug=-;
gap[]=nodenum;
while(dis[start]<nodenum)
{
loop:
for(int &i=cur[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].cap&&dis[u]==dis[v]+)
{
if(aug==-||aug>edge[i].cap)
aug=edge[i].cap;
pre[v]=u;
u=v;
if(v==end)
{
maxflow+=aug;
for(u=pre[u];v!=start;v=u,u=pre[u])
{
edge[cur[u]].cap-=aug;
edge[cur[u]^].cap+=aug;
}
aug=-;
}
goto loop;
}
}
int mindis=nodenum;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].cap&&mindis>dis[v])
{
cur[u]=i;
mindis=dis[v];
}
}
if((--gap[dis[u]])==)break;
gap[dis[u]=mindis+]++;
u=pre[u];
}
return maxflow;
} char g1[][];
char g2[][];
int mat[][]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n,d;
int iCase=;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d%d",&n,&d);
init();
int tol=;
for(int i=;i<n;i++)
scanf("%s",&g1[i]);
int m=strlen(g1[]);
memset(mat,,sizeof(mat));
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(g1[i][j]>'')
{
mat[i][j]=++tol;
addedge(*tol-,*tol,g1[i][j]-'');
} int start=,end=*tol+,nodenum=*tol+;
//进行拆点，加上源点和汇点，共2*tol+2个点。
int sum=;//总数
for(int i=;i<n;i++)
{
scanf("%s",&g2[i]);
for(int j=;j<m;j++)
if(g2[i][j]=='L')
{
sum++;
addedge(start,*mat[i][j]-,);
}
}
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(mat[i][j])
{
for(int x=-d;x<=d;x++)
for(int y=abs(x)-d;y<=d-abs(x);y++)
{
int newi=i+x;
int newj=j+y;
if(newi<||newi>=n||newj<||newj>=m)continue;
if(mat[newi][newj]==)continue;
if(newi==i&&newj==j)continue;
addedge(*mat[i][j],*mat[newi][newj]-,INF);
}
if(i<d||j<d||n-i<=d||m-j<=d)
addedge(*mat[i][j],end,INF);
}
int ans=sum-sap(start,end,nodenum);
if(ans==)printf("Case #%d: no lizard was left behind.\n",iCase);
else if(ans==)printf("Case #%d: 1 lizard was left behind.\n",iCase);
else printf("Case #%d: %d lizards were left behind.\n",iCase,ans);
}
return ;
}
2015/5/26