题目链接：

https://www.luogu.org/problemnew/show/P2472

分析：

这道题用最大流解决。

首先构建模型。

一根柱子可以跳入和跳出，于是拆成两个点：入点和出点。

每一根柱子的入点和出点连一条流量为高度的边，来限制蜥蜴跳入的次数。

当柱子a可以调到柱子b时，就从a的出点向b的入点连边，流量inf。

S向所有有蜥蜴的柱子的入点连边，流量为1

T表示地图外一点，当一根柱子能跳到地图外时，则出点向T连流量为inf的边。

然后跑最大流即可。

这里要注意数组的范围以及拆点。

代码：

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

#include<iostream>

#define inf 0x7fffffff

using namespace std;

int s,t,ans;

int d[1005];

struct edge

{

	int to,val,rev;

	edge(int _to,int _val,int _rev)

	{

		to=_to;

		val=_val;

		rev=_rev;

	}

};

vector<edge>e[1005];

void add(int x,int y,int w)

{

	e[x].push_back(edge(y,w,e[y].size()));

	e[y].push_back(edge(x,0,e[x].size()-1));

}

bool bfs()

{

    memset(d, -1, sizeof(d));

    queue<int> q;

    q.push(s);

    d[s]=0;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=0;i<e[x].size();i++)

        {

            int y=e[x][i].to;

            if(d[y]==-1 && e[x][i].val)

            {

                q.push(y);

                d[y]=d[x]+1;

            }

        }

    }

    if(d[t]==-1)

        return 0;

    else

        return 1;

}

int dfs(int x,int low)

{

    if(x==t || low==0)

        return low;

    int totflow=0;

    for(int i=0;i<e[x].size();i++)

    {

        int y=e[x][i].to;

        int rev=e[x][i].rev;

        if(d[y]==d[x]+1 && e[x][i].val)

        {

            int a=dfs(y,min(low,e[x][i].val));

            e[x][i].val-=a;

            e[y][rev].val+=a;

            low-=a;

            totflow+=a;

            if(low==0)

                return totflow;

        }

    }

    if(low!=0)

        d[x]=-1;

    return totflow;

}

void dinic()

{

	while(bfs())

	{

		ans+=dfs(s,inf);

	}

}

int main()

{

	int n,m,c,cnt=0;

	char ss;

	scanf("%d%d%d",&n,&m,&c);

	s=0,t=n*m*2+1;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			cin>>ss;

			if(ss>'0')

			{

				add((i-1)*m+j,(i-1)*m+j+n*m,ss-'0');

			}

		}

	}

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			cin>>ss;

			if(ss=='L')

			{

				add(s,(i-1)*m+j,1);

				cnt++;

			}

		}

	}

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			if(i+c>n||i-c<1||j+c>m||j-c<1)

			{

				add((i-1)*m+j+n*m,t,inf);

			}

		}

	}

	for(int x1=1;x1<=n;x1++)

	{

		for(int y1=1;y1<=m;y1++)

		{

			for(int x2=1;x2<=n;x2++)

			{

				for(int y2=1;y2<=m;y2++)

				{

					if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=c*c)

					{

						add((x1-1)*m+y1+n*m,(x2-1)*m+y2,inf);

					}

				}

			}

		}

	}

	dinic();

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

	return 0;

}

巴特西

洛谷P2472 [SCOI2007]蜥蜴题解

题目链接：

分析：

代码：

最新文章

热门文章

巴特西

洛谷P2472 [SCOI2007]蜥蜴 题解

题目链接：

分析：

代码：

最新文章

热门文章

洛谷P2472 [SCOI2007]蜥蜴题解