【bzoj1066】[SCOI2007]蜥蜴

2015.06.11 11:14 Thu | 26次阅读 | 旧日oi | 固定链接 | 源码

Description

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

题解

很裸的网络流模型,拆点简图求最大流就行了,只要往网络流这一想就OK了

我的程序

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
#define pos(x,y) ((x-1)*m+y)
int n,m,d,S,T;
char s[25];
struct edge
{
    int to,next,flow;
}e[1000005];
int h[1005],tp;
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp++;
}
void add(int u,int v,int w)
{
    ae(u,v,w);ae(v,u,0);
}
int sqr(int x)
{
    return x*x;
}
bool inrange(int x,int y)
{
    if(x<1||y<1) return 0;
    if(x>n||y>m) return 0;
    return 1;
}
void build(int x,int y)
{
    int flag=0;
    for(int i=max(x-d,0);i<=min(n+1,x+d);i++)
    for(int j=max(y-d,0);j<=min(m+1,y+d);j++)
    if(sqr(i-x)+sqr(j-y)<=d*d)
    {
        if(x==i&&y==j) continue;
        if(!inrange(i,j))
        {
            if(!flag) flag=1,add(pos(x,y)+n*m,T,inf);
        }
        else add(pos(x,y)+n*m,pos(i,j),inf);
    }
}
int dis[1005];
queue<int> q;
bool bfs()
{
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty()) q.pop();q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int cost=0,tmp;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(e[i].flow,limit-cost));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) ret+=dfs(S,inf);
    return ret;
}
int main()
{
    //freopen("lizard.in", "r", stdin);
    //freopen("lizard.out", "w", stdout);
    cin>>n>>m>>d;S=0;T=2*n*m+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++)
    {
        for(int x,j=1;j<=m;j++)
        {
            scanf("%1d",&x);
            if(x) add(pos(i,j),pos(i,j)+n*m,x);
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
        if(s[j]=='L') sum++,add(S,pos(i,j),1);
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    build(i,j);
    printf("%d\n",sum-dinic());
    fclose(stdin);
    fclose(stdout);
    return 0;
}```