BZOJ 1066 [SCOI2007]蜥蜴建模+网络流

本文主要是介绍BZOJ 1066 [SCOI2007]蜥蜴建模+网络流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

　　在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃
到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石
柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不
变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个
石柱上。

Input

　　输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱
，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。

Output

　　输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........

Sample Output

HINT

100%的数据满足：1<=r, c<=20, 1<=d<=4

Source

题目链接

这题作为网络流的入门题目还是可以的。

此题就是一道建模题。

首先说一下距离d不是曼哈顿距离。。。是欧拉距离。。。勾股那个。

此题的思想很简单，裂点，一个高度为x的石柱可以看成编号i->j，其中C(i,j)=x。

那么对于第(i,j)个石柱如何裂呢？如果说i从1开始计算，j从0开始，那么

now=r*2*(i-1)+2*j，

然后这个点可以分为“出点”和“入点”，分别是now+1和now+2。

所有其他点和它相连时，now+1连向别的点，别的点连向now+2.

最后建立一个超级源节点s和超级汇节点t。

s连向所有L处的入点，所有能够通过距离d跳到格子外部的出点连向t。

所以空间我们要开r*c*2+2.

接下来就是跑最大流的过程……

ISAP里面gap优化总是要漏一句。。。我说怎么TLE了呢。。

开的空间注意一下，，特别是边数等等。

我Map（输入数组）的空间开大了一点点，防止数据不好导致我查不出错。。。

代码有点长~~，有点丑~~

建图有点难受，，不过其实虽然长但是看起来应该挺好懂的吧。

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int MAX=200,inf=10,VerMax=2000,EdgMax=10000;
int r,c,dd,Ecnt,sumxy,Ver;
int source,sink;
int cur[VerMax],pre[VerMax],d[VerMax];
int Q[EdgMax],gap[EdgMax];
int Map[MAX][MAX];
struct Edge{int next,to,C;
}E[2000000];int head[VerMax];
int dist(int x,int y){return x*x+y*y;
}
int vertexb(int i,int j){return r*2*(i-1)+2*j;
}
void add(int u,int v,int w){E[Ecnt].next=head[u];E[Ecnt].to=v;E[Ecnt].C=w;head[u]=Ecnt++;
}
bool out(int x,int y){y++;for (int i=0;i<=c;i++)if (dist(0-x,i-y)<=dd*dd) return 1;for (int i=0;i<=r;i++)if (dist(0-y,i-x)<=dd*dd) return 1;for (int i=1;i<=c+1;i++)if (dist(r+1-x,i-y)<=dd*dd) return 1;for (int i=1;i<=r+1;i++)if (dist(c+1-y,i-x)<=dd*dd) return 1;return 0;
}
void build(){char tmp[MAX]; Ecnt=0;memset(head,255,sizeof(head));for (int i=1;i<=r;i++)for (int j=0;j<c;j++)if (Map[i][j]){int now=vertexb(i,j);add(now+2,now+1,Map[i][j]);add(now+1,now+2,0);}for (int i=1;i<=r;i++)for (int j=0;j<c;j++){if (!Map[i][j]) continue;int nowb=vertexb(i,j),now;for (int x=1;x<=r;x++)for (int y=0;y<c;y++)if (Map[x][y] && (x!=i || y!=j))if (dist(x-i,y-j)<=dd*dd){now=vertexb(x,y);add(nowb+1,now+2,inf);add(now+2,nowb+1,0);add(now+1,nowb+2,inf);add(nowb+2,now+1,0);}}sumxy=0;int Max=vertexb(r,c-1)+2;for (int i=1;i<=r;i++){scanf("%s",tmp);for (int j=0;j<c;j++)if (tmp[j]=='L'){sumxy++;int now=vertexb(i,j);add(Max+1,now+2,1);add(now+2,Max+1,0);}}for (int i=1;i<=r;i++)for (int j=0;j<c;j++)if (Map[i][j] && out(i,j)){int now=vertexb(i,j);add(now+1,Max+2,inf);add(Max+2,now+1,0);}source=Max+1;sink=Max+2;
}
void BFS(){memset(gap,0,sizeof(gap));memset(d,255,sizeof(d));gap[0]=1; d[sink]=0;int Head=0,tail=1;Q[0]=sink;while (Head!=tail){int u=Q[Head++];for (int i=head[u];~i;i=E[i].next){int j=E[i].to;if (~d[j]) continue;d[j]=d[u]+1;gap[d[j]]++;Q[tail++]=j;}}
}
int ISAP(){BFS();memcpy(cur,head,sizeof(cur));int u,flow=0;u=pre[source]=source;while (d[sink]<Ver+1){if (u==sink){int f=inf,neck;for (int i=source;i!=sink;i=E[cur[i]].to)if (f>E[cur[i]].C)neck=i,f=E[cur[i]].C;for (int i=source;i!=sink;i=E[cur[i]].to)E[cur[i]].C-=f,E[cur[i]^1].C+=f;flow+=f;u=neck;}int j;for (j=cur[u];~j;j=E[j].next)if (E[j].C && d[E[j].to]+1==d[u]) break;if (~j){cur[u]=j;pre[E[j].to]=u;u=E[j].to;}    else{if (!(--gap[d[u]])) break;int mind=Ver+1;for (int i=head[u];~i;i=E[i].next)if (E[i].C && mind>d[E[i].to])cur[u]=i,mind=d[E[i].to];d[u]=mind+1;gap[d[u]]++;u=pre[u];}}return flow;
}
int main(){r=read(),c=read(),dd=read();char tmp[MAX];Ver=0;for (int i=1;i<=r;i++){scanf("%s",tmp);for (int j=0;j<c;j++){Map[i][j]=tmp[j]-48;if (Map[i][j]) Ver++;}}Ver*=2; Ver+=2;build();printf("%d\n",sumxy-ISAP());
}

这篇关于BZOJ 1066 [SCOI2007]蜥蜴建模+网络流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！