题解 P4474 【王者之剑】
RemiliaScar1et
2021-02-19 21:48:02
### 解析
~~大家做法都差不多呀,我来给个详细证明吧~~
我们观察一下这个问题的某些 ~~显然的~~ 特殊性质
首先,我们只能在偶数秒拿到宝石。奇数秒走到的格子已经被上一个偶数秒清空了。
而且我们不能同时拿到相邻格子上的两个宝石。原因同上。
这个时候已经有点独立集那味了。我们若是把相邻的格子黑白染色并连上边,那么最优方案选出来的点就组成一个独立集,还是二分图的最大点权独立集。其实我们可以看出,每种合法方案都可以转化这个二分图的一个独立集。
但是每个独立集都是一个合法方案吗?这可不一定。我们需要证明出来。
怎么去考虑?最好的方法是对任意独立集直接构造一个合法方案出来。
我们先把每一行看做一个阶段,用 “S” 形路线试着挨个遍历每个阶段。以下图一个 $6\times 6$ 的矩阵举例
![](https://img.imgdb.cn/item/602fa5aae7e43a13c690925e.png)
标灰色的点是独立集中的点,也就是我们要取到的点。
进入 $A2$ 时一定是偶数秒,进入$A3$ 是奇数秒,进入 $A4$ 是偶数秒,如果我们要保证能拿到 $A5$ 那我们就要在 $A3$ 停顿一秒,但是我们一停顿就会将我们接下来要取的 $B3$ 给炸了。并且在其他任何地方停顿都无法保证任意一个的灰点都能够被取到。所以这种构造方式不可行。
但是我们不一定要遍历所有的格子。我们若是每两行为一个阶段,在遍历第一行时连着第二行的一起取完。然后不遍历第二行就可以防止影响下个阶段。可按照如下方式构造:
1. 按遍历方向顺序,依次取宝石。 ~~(废话)~~
2. 第一行的宝石在偶数秒时直接进入格子获取。
3. 第二行的宝石我们要在奇数秒时进入其在第一行的对应格子,然后在偶数秒进入格子取宝石,之后立即返回第一行对应格子,奇偶性没有改变。
来实际操作一下:
![](https://img.imgdb.cn/item/602fac8be7e43a13c693aa2d.png)
我们可以看到,当到达 $A3$ 时,我们直接上去拿到 $B3$ ,用时两秒,时间奇偶性没变。$A5$ 要求在偶数秒进入,那我们就在 $A3$ 停顿一秒。由于 $B3$ 已经拿了,所以没有影响。同样的,我们应在奇数秒进入 $C6$ ,以便取到 $D6$ ,取完 $D6$ 回到 $C6$ 时还是奇数秒,可以顺利取到 $C5$。
试着证它能否取到所有独立集的点。
首先,阶段之间是没有冲突的。我们只有在第二行有灰点时才去第二行,由独立集的性质能知道下一阶段第一行对应位置是没有灰点的。
其次我们需证,对于阶段内的点,必定有一个操作序列能够取到所有的点。
我们将每个格子的要求序列化。对于阶段的第一行,将灰点所在位置设为 $0$ ,代表这个点必须偶数秒进入;将第二行有对应灰点的位置设为 $1$ ,代表必须在奇数时进入这个点;其他的点都设为 $?$ ,假装我们不知道。
就举上面 $Phase\ 1$ 的例子。
![](https://img.imgdb.cn/item/602fb0a8e7e43a13c6958537.png)
构造出来一个序列 $?,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
```cpp
#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;
}
```
### 参考文献
胡伯涛 — 《最小割模型在信息学奥赛中的应用》