题解 - P2472 [SCOI2007]蜥蜴

· · 个人记录 

题目背景
07四川省选

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

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

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

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

输入输出样例
输入样例#1： 
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
输出样例#1： 
1
说明
100%的数据满足：1<=r, c<=20, 1<=d<=4

思路：

把每一个石柱都分成两个点：入口和出口。

一共有四种建边方式——

  1. 初始化一个源点S，它连着蜥蜴所在的位置，因为只有一个蜥蜴，so容量为1。
  2. 自己的入口连上自己的出口，容量为石柱高度，表示能跳走的个数。
  3. 其他的石柱在跳跃范围内，都能跳上这个石柱，所以其他石柱出口就和这个石柱入口建边，容量为inf。
  4. 最后能到汇点T的石柱，容量为inf。

再跑网络流即可

#include<bits/stdc++.h>
using namespace std;
int nex[500005],go[500005],head[500005],cnt[500005],w[500005],bi=1,lev[500005],a[1000][1000];
int n,m,d,S,T;
long long ans=0;
char sss[1000][1000];
void add(int x,int y,int v)
{
    nex[++bi]=head[x];
    head[x]=bi;
    go[bi]=y;
    w[bi]=v;
}
bool bfs()
{
    memset(lev,-1,sizeof(lev));
    cnt[0]=1;lev[T]=0;
    queue <int> q;
    q.push(T);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nex[i])
        {
            if(lev[go[i]]==-1)
            {
                ++cnt[lev[go[i]]=lev[u]+1] ;
                q.push(go[i]);
            }
        }
    }
}
int wrx(int u,int flow)
{
    if(u==T)
    {
        ans+=flow;
        return flow;
    }
    int res=0,v,sum=0;
    for(int i=head[u];i;i=nex[i])
    {
        v=go[i];
        if(w[i]&&lev[u]-1==lev[v])
        {
            sum=wrx(v,min(w[i],flow-res));
            if(sum)
            {
                w[i]-=sum;
                w[i^1]+=sum;
                res+=sum;
            }
            if(flow==res)
            return res;
        }
    }
    if(!--cnt[lev[u]])
    lev[S]=T+1;
    ++cnt[++lev[u]];
    return res;
}
int main()
{
    cin>>n>>m>>d;
    S=0;
    T=n*m*2+2;//一共那么多点 
    int tot=0;
    for(int i=1;i<=n;i++)
    {   
        scanf("%s",sss[i]+1);
        for(int j=1;j<=m;j++)
        {
            a[i][j]=sss[i][j]-48;
            if(a[i][j])
            {
                add((i-1)*m+j,(i-1)*m+j+n*m,a[i][j]);//自己入点和出点连边，只能过a[i][j] 
                add((i-1)*m+j+n*m,(i-1)*m+j,0);//反向连边 
            }
        }

    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(i<=d||j<=d||(n-i)<d||(m-j)<d)
            {
                add((i-1)*m+j+n*m,T,1e9);//符合条件的出边 
                add(T,(i-1)*m+j+n*m,0);
            }
    }
    int aans=0;
    char ss[50][50];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ss[i]+1);
        for(int j=1;j<=m;j++)
         {
            if(ss[i][j]=='L')
            {
                aans++; 
                add(0,(i-1)*m+j,1);//入边只能为1，不可能同一个网址有两只 
                add((i-1)*m+j,0,0);
            }
         }
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        for(int k=1;k<=n;k++)
          for(int l=1;l<=m;l++)
        {
            if((i-k)*(i-k)+(j-l)*(j-l)<=d*d)
            {
                add((i-1)*m+j+n*m,(k-1)*m+l,1e9);//如果可以连边（从一个出边到入边可以是无限个 
                add((k-1)*m+l,(i-1)*m+j+n*m,0);
            }
        }
    bfs();//网络流板子 
    while(lev[S]<T)
    {
        wrx(S,1e9); 
    }
    cout<<aans-ans<<endl;//最多跑出ans个 
    return 0;
}