描述

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

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

输入

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

输出

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

提示

　　【限制】 100%的数据满足：1<=r, c<=20, 1<=d<=3

题解

　　这是一道网络流。

　　先考虑如何建图：对于每根石柱，我们可以把它拆成两个点，中间连一条容量为其高度的边。对于每根石柱，我们再将它和与它距离不超过d的所有石柱连边，容量无限。对于每根能够跳出去的石柱，我们将它与汇点t相连。对于每根有蜥蜴的石柱，我们将源点s与它相连。这样我们就可以跑最大流了。放上代码：

#include<bits/stdc++.h>

using namespace std;

#define N 100010

#define INF 0x3f3f3f3f

int r,c,d;

int num=,f[N];

struct node{

    int u,v,w,nxt;

}e[N<<];

void add(int u,int v,int w){

    e[++num]=(node){u,v,w,f[u]};f[u]=num;

    e[++num]=(node){v,u,,f[v]};f[v]=num;

}

//build graph

int s,t,dis[N];

int bfs(){

    queue<int>q;

    memset(dis,-,sizeof(dis));

    q.push(s);dis[s]=;

    while(!q.empty()){

        int u=q.front();q.pop();

        for(int i=f[u];i;i=e[i].nxt){

            int v=e[i].v,w=e[i].w;

            if(w&&dis[v]==-){

                dis[v]=dis[u]+;q.push(v);

                if(v==t) return ;

            }

        }

    }

    return ;

}

int dfs(int u,int flow){

    if(u==t||!flow) return flow;

    int ret=;

    for(int i=f[u];i;i=e[i].nxt){

        int v=e[i].v;

        if(e[i].w&&dis[v]==dis[u]+){

            int w=dfs(v,min(e[i].w,flow));

            if(!w) continue;

            ret+=w;flow-=w;e[i].w-=w;e[i^].w+=w;

            if(!flow) break;

        }

    }

    if(!ret) dis[u]=-;

    return ret;

}

int dinic(){

    int mf=;

    while(bfs()){mf+=dfs(s,INF);}

    return mf;

}

//flow

int cnt,id[][][],mp[][];

char ch[];

int dist(int xx,int yy){return xx*xx+yy*yy;}

int ID(int i,int j){return (i-)*c+j;}

int main(){

    scanf("%d%d%d",&r,&c,&d);s=;t=(r*c)<<|;

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

        scanf("%s",ch+);

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

            mp[i][j]=ch[j]-'';

            id[i][j][]=ID(i,j);id[i][j][]=id[i][j][]+r*c;

            if(mp[i][j]) add(id[i][j][],id[i][j][],mp[i][j]);

        }

    }

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

        scanf("%s",ch+);

        for(int j=;j<=c;j++){if(ch[j]=='L') cnt++,add(s,id[i][j][],);}

    }

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

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

            if(!mp[i][j]) continue;

            if(i<=d||j<=d||r-i+<=d||c-j+<=d) add(id[i][j][],t,INF);

            for(int dx=-d;dx<=d;dx++){

                int xx=i+dx;

                if(xx<||xx>r) continue;

                for(int dy=-d;dy<=d;dy++){

                    int yy=j+dy;

                    if(yy<||yy>c||!mp[xx][yy]||dist(xx-i,yy-j)>d*d) continue;

                    if(xx==i&&yy==j) continue;

                    add(id[i][j][],id[xx][yy][],INF);

                }

            }

        }

    }

    printf("%d",cnt-dinic());

    return ;

}

巴特西

WOJ#1243 蜥蜴 lizard

描述

输入

输出

提示

题解

最新文章

热门文章