Description

在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃

到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石

柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不

变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个

石柱上。

Solution

把点拆成一个入点一个出点，之间连一条容量为高度的边作为限制

源向蜥蜴连容量为1的边，每个点能到达的地方由出点向入点连INF的边，能跳到汇的点向汇连INF的边

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define eps 1e-9#define INF 0x3f3f3f3f#define pos(x,y) ((x-1)*c+y)using namespace std;int r,c,d,s,t,head[1000],level[1000],cnt=0,liz=0;struct Node{ int next,to,cap;}Edges[100005];void addedge(int u,int v,int c){ Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; Edges[cnt].cap=c; cnt++;}void insert(int u,int v,int c){ addedge(u,v,c); addedge(v,u,0);}int dcmp(double x){ if(fabs(x)<=eps)return 0; return x>0?1:-1; }double dis(int x1,int y1,int x2,int y2){ return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}bool bfs(){ memset(level,-1,sizeof(level)); level[s]=0; queue
           
            q; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==-1&&Edges[i].cap) {level[v]=level[u]+1;q.push(v);} } } if(level[t]==-1)return false; return true;}int dfs(int u,int flow){ int f=0,d=0; if(u==t)return flow; for(int i=head[u];~i&&f
            
             r||j<=d||j+d>c) insert(r*c+pos(i,j),t,INF); } } for(int i=1;i<=r;i++) { scanf("%s",S[i]+1); for(int j=1;j<=c;j++) { if(S[i][j]=='L') ++liz,insert(s,pos(i,j),1); } } int ans=liz,d=0; while(bfs()) { while(d=dfs(s,INF)) ans-=d; } printf("%d\n",ans); return 0;}