luogu2472 蜥蜴

S1

我一开始TM以为这道题这么水是不用写解题报告的……
不过为了~~我的无脑错误中表现出的zz本质~~介绍网络流的特性还是写一个吧。
这道题建图其实蛮容易的，就是建图的代码不是很好打。从源点向每个蜥蜴所在的点连一条边长为1的边，然后把每个点拆成两个，自连自的边是石柱的高度，拆成的两个点一个连接跳进来的，一个连接跳出去的，边权都是inf，能跳出地图的点连接汇点，边权inf。结合之前的想法，用最小割来理解，和源点相连的就是没能跳出去的蜥蜴。
上交代码，咦？WA了一个点？

S2

自己检查了半天，又让宽嫂来卡了半天玄学，一直不过……懵逼的我一度以为自己建图的思路出了问题……
又zz地自查了半天之后发现了错误。
在底下的程序中有一处是连双向边的，就是一个点能跳到另一个点，所以它们之间应该是双向边。我用了一个四重循环，没有判重，所以分成两次单向边来加。这样其实是错误的，因为之前我们说到过我们要拆点，所以对于同一个点，连进来的边和连出去的边不作用于同一个点。错误的地方我会在代码中标出来。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,k,cnt,d,head[500000],cur[500000],dis[500000],ans,tot,s=0,t=10001,a[1001][1001];
string st;
struct node
{
    int from,to,dis,num,next;
}ljb[500000];
inv add_edge(int x,int y,int z)
{
    ljb[++cnt].from=x;
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    ljb[cnt].next=head[x];
    head[x]=cnt;
}
inv add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
inb can(int i,int j,int k,int l)
{
	if (i<k) swap(i,k);
	if (j<l) swap(j,l);
	int x=i-k;
	int y=j-l;
	if ((x*x+y*y)<=d*d) return 1;
	return 0;
}
int main()
{
	scanf("%d%d%d",&n,&m,&d);
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=n;i++)
	{
		cin>>st;
		for (rint j=1;j<=m;j++)
		{
			a[i][j]=st[j-1]-'0';
			if (a[i][j])
			{
				int y=(i-1)*m+j;
				add(y,y+500,a[i][j]);
				if (i<=d || n-i+1<=d || j<=d || m-j+1<=d)
					add(y+500,t,big);
			}
		}
	}
	int num=0;
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=m;j++)
		{
			char c;cin>>c;
			if (c=='L') add(s,(i-1)*m+j,1),num++;
		}
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=m;j++)
			if (a[i][j])
			{
				for (rint k=i-d;k<=i+d;k++)
					for (rint l=j-d;l<=j+d;l++)
						if (a[k][l] && (i!=k || j!=l))
						{
							int x=(i-1)*m+j;
							int y=(k-1)*m+l;
							if (can(i,j,k,l)) add(x+500,y,big);
							//这就是我犯傻的地方↑ 
						}
			}
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		} 
		while (tot);
	}
	printf("%d",num-ans);
}