BZOJ1066 [SCOI2007]蜥蜴

题意：

给定一个网格图和限定蜥蜴的跳跃距离，图上有一些格子有石柱，柱子的高度是可以最多经过的次数，且每格子上最多站一只蜥蜴，问最少有多少只蜥蜴逃不出去。

知识点：

最大流

解法：

正难则反，考虑如何计算最多多少只蜥蜴逃得出去，用总数减去即可。源点连向每只蜥蜴为1，将每个石柱的点拆点，次数多少拆多少个点，每个小点之间又拆两个中间连1，表示限制容量只能经过一次。蜥蜴连向所在位置的第一个点，然后判断能走出边界的石柱点有多少个，那些点的右边连向汇点。最后每个石柱到曼哈顿距离在范围内的石柱连边，注意假如目标石柱上面一开始就有蜥蜴，那么只能从第二个点开始连，否则第一个点开始连。跑最大流即可。

备注：

有一个简化的做法是不拆石柱的点，但是也是变成两个小点中间连最大次数作为容量限制；右边的点同样连到范围内的点的左边，右边的点假如可以到边界的，连最大次数的边到汇点。

代码：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn=2810,inf=0x7fffffff;
int n,m,d,S,T,tot,head[maxn],h[25][25],dis[maxn],cur[maxn],cnt,mp[25][25],id[25][25][3],num,sum;
queue<int>q;
char c[25];
struct node
{
    int nxt,to,w;
}edge[maxn*80];

void add(int u,int v,int w)
{
    edge[++tot]=(node){head[u],v,w};
    head[u]=tot;
}

void link(int u,int v,int w)
{
    add(u,v,w);
    add(v,u,0);
}

bool bfs()
{
    memset(dis,0,sizeof(dis));
    while (!q.empty())
        q.pop();
    int i,u,v;
    q.push(S);
    dis[S]=1;
    while (!q.empty())
    {
        u=q.front();
        q.pop();
        for (i=head[u];i;i=edge[i].nxt)
        {
            v=edge[i].to;
            if (!dis[v]&&edge[i].w>0)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[T];
}

int dfs(int u,int flow)
{
    if (u==T)
        return flow;
    int v,res=flow,tmp;
    for (int &i=cur[u];i;i=edge[i].nxt)
    {
        v=edge[i].to;
        if (dis[v]==dis[u]+1&&edge[i].w>0)
        {
            tmp=dfs(v,min(res,edge[i].w));
            edge[i].w-=tmp;
            edge[i^1].w+=tmp;
            res-=tmp;
            if (!res)
                break;
        }
    }
    return flow-res;
}

int dinic()
{
    int ans=0,tmp=0,i;
    while (bfs())
    {
        for (i=1;i<=T;i++)
            cur[i]=head[i];
        tmp=dfs(S,inf);
        if (!tmp)
            break;
        ans+=tmp;
    }
    return ans;
}

int mabs(int x)
{
    if (x<0)
        return -x;
    return x;
}

int main()
{
    int i,j,k,x,y,u,v;
    scanf("%d%d%d",&n,&m,&d);
    tot=1;
    for (i=1;i<=n;i++)
    {
        scanf("%s",c+1);
        for (j=1;j<=m;j++)
            h[i][j]=c[j]-'0',num+=h[i][j];
    }
    for (i=1;i<=n;i++)
    {
        scanf("%s",c+1);
        for (j=1;j<=m;j++)
            if (c[j]=='L')
                mp[i][j]=(++cnt);
    }
    S=cnt+num*2+1,T=S+1;
    sum=cnt-1;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            for (k=0;k<=h[i][j]-1;k++)
            {
                sum+=2,id[i][j][k]=sum;
                link(sum,sum+1,1);
            }
            if (mp[i][j])
            {
                link(S,mp[i][j],1);
                link(mp[i][j],id[i][j][0],1);
            }
            if (i<=d||i>=n-d+1||j<=d||j>=m-d+1)
            {
                for (k=0;k<=h[i][j]-1;k++)
                    link(id[i][j][k]+1,T,1);
            }
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            for (x=max(1,i-d);x<=min(n,i+d);x++)
                for (y=max(1,j-d);y<=min(m,j+d);y++)
                    if ((i!=x||j!=y)&&mabs(i-x)+mabs(j-y)<=d)
                        for (u=0;u<=h[i][j]-1;u++)
                            for (v=(mp[x][y]>0?1:0);v<=h[x][y]-1;v++)
                                link(id[i][j][u]+1,id[x][y][v],1);
    printf("%d\n",cnt-dinic());
    return 0;
}

BZOJ1066 [SCOI2007]蜥蜴

原文：https://www.cnblogs.com/Ronald-MOK1426/p/12303371.html