题解 P4474 【王者之剑】

### 解析 ~~大家做法都差不多呀，我来给个详细证明吧~~ 我们观察一下这个问题的某些 ~~显然的~~ 特殊性质 首先，我们只能在偶数秒拿到宝石。奇数秒走到的格子已经被上一个偶数秒清空了。 而且我们不能同时拿到相邻格子上的两个宝石。原因同上。 这个时候已经有点独立集那味了。我们若是把相邻的格子黑白染色并连上边，那么最优方案选出来的点就组成一个独立集，还是二分图的最大点权独立集。其实我们可以看出，每种合法方案都可以转化这个二分图的一个独立集。 但是每个独立集都是一个合法方案吗？这可不一定。我们需要证明出来。 怎么去考虑？最好的方法是对任意独立集直接构造一个合法方案出来。 我们先把每一行看做一个阶段，用 “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 ```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; } ``` ### 参考文献 胡伯涛 — 《最小割模型在信息学奥赛中的应用》