蜥蜴_bzoj1066_最大流

2017-01-06 07:57:40来源:CSDN作者:jpwang8人点击

第七城市

Description


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

Input


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

Output


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

Analysis


  1. 网络流
  2. 每根柱子有限制所以拆点,连边是它的高度
  3. 每根柱子只有一只蜥蜴所以源点和蜥蜴连边是1
  4. 柱子随便走所以能相互到达的柱子连边INF
  5. 所有能一步跳出的柱子连汇点
  6. 比较神奇的是dinic死活过不了,cin>>string也会,至今仍不知错在何处,(尴尬脸

Code


#include <cstring>#include <string>#include <cstdio>#include <queue>#define rep(i, st, ed) for (int i = st; i <= ed; i ++)#define fill(x, t) memset(x, t, sizeof(x))#define N 2048#define R 31#define E 16384#define INF 0x3f3f3f3fusing namespace std;int vis[N], t[N][N], map[R][R];int min(int x, int y){    return x<y?x:y;}int dist(int x, int y){    return (x * x + y * y);}int getPoint(int m, int x, int y){    return m * (x - 1) + y;}int find(int now, int ed, int mn){    vis[now] = 1;    if (ed == now){        return mn;    }    rep(i, 0, ed){        if (t[now][i] > 0 && !vis[i]){            int d = find(i, ed, min(mn, t[now][i]));            if (d > 0){                t[now][i] -= d;                t[i][now] += d;                return d;            }        }    }    return 0;}int dinic(int st, int ed){    int mxFlow = 0;    fill(vis, 0);    while (int d = find(st, ed, INF)){        mxFlow += d;        fill(vis, 0);    }    return mxFlow;}int main(void){    int n, m, d;    scanf("%d%d%d",&n,&m,&d);    int st = n * m * 2 + 1;    int ed = n * m * 2 + 2;    rep(i, 1, n){        char s[31];        scanf("%s",s);        rep(j, 1, m){            map[i][j] = s[j - 1] - '0';            if (map[i][j] != 0){                t[getPoint(m, i, j) * 2 - 1][getPoint(m, i, j) * 2] = map[i][j];            }        }    }    int tot = 0;    rep(i, 1, n){        char s[31];        scanf("%s",s);        rep(j, 1, m){            if (s[j - 1] == 'L'){                t[st][getPoint(m, i, j) * 2 - 1] = 1;                tot ++;            }        }    }    rep(i, 1, n){        rep(j, 1, m){            if (map[i][j]){                rep(k, 1, n){                    rep(l, 1, m){                        if ((i != k || j != l) && map[k][l] != 0 && dist((i - k), (j - l)) <= d * d){                            t[getPoint(m, i, j) * 2][getPoint(m, k, l) * 2 - 1] = INF;                            t[getPoint(m, k, l) * 2][getPoint(m, i, j) * 2 - 1] = INF;                        }                    }                }            }        }    }    rep(i, 1, n){        rep(j, 1, m){            if (map[i][j] != 0 && (i <= d || (n - i + 1) <= d || j <= d || (m - j + 1) <= d)){                t[getPoint(m, i, j) * 2][ed] = INF;            }        }    }    int ans = dinic(st, ed);    printf("%d/n",tot - ans);    return 0;}
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台