自动搬运

查看原文

来自洛谷，原作者为

	RemiliaScar1et 永远に赤い幼き月

搬运于2025-08-24 22:00:33，当前版本为作者最后更新于2021-02-19 21:48:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解析

大家做法都差不多呀，我来给个详细证明吧

我们观察一下这个问题的某些 显然的 特殊性质

首先，我们只能在偶数秒拿到宝石。奇数秒走到的格子已经被上一个偶数秒清空了。

而且我们不能同时拿到相邻格子上的两个宝石。原因同上。

这个时候已经有点独立集那味了。我们若是把相邻的格子黑白染色并连上边，那么最优方案选出来的点就组成一个独立集，还是二分图的最大点权独立集。其实我们可以看出，每种合法方案都可以转化这个二分图的一个独立集。

但是每个独立集都是一个合法方案吗？这可不一定。我们需要证明出来。

怎么去考虑？最好的方法是对任意独立集直接构造一个合法方案出来。

我们先把每一行看做一个阶段，用 “S” 形路线试着挨个遍历每个阶段。以下图一个 $6\times 6$ 的矩阵举例

标灰色的点是独立集中的点，也就是我们要取到的点。

进入 $A2$ 时一定是偶数秒，进入$A3$ 是奇数秒，进入 $A4$ 是偶数秒，如果我们要保证能拿到 $A5$ 那我们就要在 $A3$ 停顿一秒，但是我们一停顿就会将我们接下来要取的 $B3$ 给炸了。并且在其他任何地方停顿都无法保证任意一个的灰点都能够被取到。所以这种构造方式不可行。

但是我们不一定要遍历所有的格子。我们若是每两行为一个阶段，在遍历第一行时连着第二行的一起取完。然后不遍历第二行就可以防止影响下个阶段。可按照如下方式构造：

1. 按遍历方向顺序，依次取宝石。 (废话)
2. 第一行的宝石在偶数秒时直接进入格子获取。
3. 第二行的宝石我们要在奇数秒时进入其在第一行的对应格子，然后在偶数秒进入格子取宝石，之后立即返回第一行对应格子，奇偶性没有改变。

来实际操作一下：

我们可以看到，当到达 $A3$ 时，我们直接上去拿到 $B3$ ，用时两秒，时间奇偶性没变。$A5$ 要求在偶数秒进入，那我们就在 $A3$ 停顿一秒。由于 $B3$ 已经拿了，所以没有影响。同样的，我们应在奇数秒进入 $C6$ ，以便取到 $D6$ ，取完 $D6$ 回到 $C6$ 时还是奇数秒，可以顺利取到 $C5$。

试着证它能否取到所有独立集的点。

首先，阶段之间是没有冲突的。我们只有在第二行有灰点时才去第二行，由独立集的性质能知道下一阶段第一行对应位置是没有灰点的。

其次我们需证，对于阶段内的点，必定有一个操作序列能够取到所有的点。

我们将每个格子的要求序列化。对于阶段的第一行，将灰点所在位置设为 $0$ ，代表这个点必须偶数秒进入；将第二行有对应灰点的位置设为 $1$ ，代表必须在奇数时进入这个点；其他的点都设为 $?$ ，假装我们不知道。

就举上面 $Phase\ 1$ 的例子。

构造出来一个序列 $?,0,1,?,0,?$

根据“不能同时拿到相邻格子上的两个宝石”的推论，该序列不应该存在连续的两个 $0$ 或 $1$ 必然是 $01$ 相间的形式。

由于对于一段连续的 $?$ 我们很容易构造序列使其只有单个 $?$，所以问题集中于非 $?$ 和 $?$ 的衔接上。

我们直接开始分类讨论。

1. $0,?,0$ 或 $1,?,1$ 我们只需要令 $?$ 为 $1$ 或 $0$ 即可。

2. $1,?,0$ ，此时我们需要在这一格停留一下，得到序列 $1,(0)1,0$

3. $0,?,1$ ，仍然是用停留解决问题，得到序列 $0,(1)0,1$ 。

综上，对于任意一个独立集，我们都可以构造出一个合法方案取到独立集内所有点。

你已经证明了每一个方案与独立集一一对应，只需要放心大胆跑网络流就可以了，快去试一试吧

code

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=2e6+10,INF=1e8;

int n,m,S,T;
int head[N],ver[M],cc[M],nxt[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int dx[5]={0,1,0,-1};
int dy[5]={-1,0,1,0};

inline int index_(int i,int j)	{return (i-1)*m+j;}

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S, d[S]=0, cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(lim-flow,cc[i]));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	S=0,T=N-10;
	memset(head,-1,sizeof head);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int x;
			scanf("%d",&x);
			sum+=x;
			if((i+j)&1)
			{
				add(S,index_(i,j),x);
				for(int k=0;k<4;k++)
				{
					int xx=i+dx[k],yy=j+dy[k];
					if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
						add(index_(i,j),index_(xx,yy),INF);
				}
			}
			else {
				add(index_(i,j),T,x);
			}
		}
	}
	printf("%d",sum-dinic());
	return 0;
}

参考文献

胡伯涛 — 《最小割模型在信息学奥赛中的应用》