【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

这大概就是我做过的最难得网络流题了（没错，我就是这么弱，你打我啊）

拆点x,x'，流量为高度，有蜥蜴的点x与S连边，容量为1，所有可以滚粗的点x‘与T连边，容量inf，所以可以互相到达的点x’，y连边，容量inf，跑最大流

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 using namespace std;

 const int inf=,N=;

 struct ee{int to,next,f;}e[];

 int head[N],q[N*],map[][],dis[N];

 int S,T,r,c,d,cnt=,ans;

 char s[];

 int sqr(int x) {return x*x;}

 int wz(int x,int y,int add){

     return ((x-)*c+y+r*c*add);

 }

 double dist(int x1,int y1,int x2,int y2){

     return sqrt(sqr(x1-x2)+sqr(y1-y2));

 }

 void ins(int u,int v,int f){

     e[++cnt].to=v;e[cnt].f=f;e[cnt].next=head[u];head[u]=cnt;

     e[++cnt].to=u;e[cnt].f=;e[cnt].next=head[v];head[v]=cnt;

 }

 int pd(int x,int y){

     if (x<=d||r-x<d||y<=d||c-y<d) return ;

     return ;

 }

 bool bfs(){

     for (int i=;i<=T;i++) dis[i]=inf;

     int h=,t=,now;

     q[]=S;dis[S]=;

     while(h!=t){

         now=q[++h];

         for (int i=head[now];i;i=e[i].next){

             int v=e[i].to;

             if (e[i].f&&dis[now]+<dis[v]){

                 dis[v]=dis[now]+;

                 if (v==T)return ;

                 q[++t]=v;

             }

         }

     }

     if (dis[T]==inf) return ; return ;

 }

 int dinic(int now,int f){

     if (now==T) return f;

     int rest=f;

     for (int i=head[now];i;i=e[i].next){

         int v=e[i].to;

         if (e[i].f&&dis[v]==dis[now]+){

             int t=dinic(v,min(rest,e[i].f));

             if (!t) dis[v]=;

             e[i].f-=t;

             e[i^].f+=t;

             rest-=t;

         }

     }

     return f-rest;

 }

 int main(){

     scanf("%d%d%d",&r,&c,&d);

     S=,T=*r*c+;

     for (int i=;i<=r;i++){

         scanf("%s",s);

         int l=strlen(s);

         for (int j=;j<l;j++) map[i][j+]=s[j]-'';

     }

     for (int i=;i<=r;i++){

         scanf("%s",s);

         int l=strlen(s);

         for (int j=;j<l;j++){

             if (s[j]=='L') ins(S,wz(i,j+,),),ans++;

         }

     }

     for (int i=;i<=r;i++)

         for (int j=;j<=c;j++)

             if (map[i][j]) ins(wz(i,j,),wz(i,j,),map[i][j]);

     for (int x1=;x1<=r;x1++)

         for (int y1=;y1<=c;y1++){

             if (!map[x1][y1]) continue;

             for (int x2=;x2<=r;x2++)

                 for (int y2=;y2<=c;y2++){

                     if (x1==x2&&y1==y2) continue;

                     if (map[x1][y1]&&map[x2][y2]&&dist(x1,y1,x2,y2)<=d){

                         ins(wz(x1,y1,),wz(x2,y2,),inf);

                         ins(wz(x2,y2,),wz(x1,y1,),inf);

                     }

                 }

             }

     for (int i=;i<=r;i++)

         for (int j=;j<=c;j++)

             if (pd(i,j)) ins(wz(i,j,),T,inf);

     while(bfs())

     ans-=dinic(S,inf);

     printf("%d",ans);

 }

秒客网