题解 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 相间的形式。

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

我们直接开始分类讨论。

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

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

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

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;
}

参考文献

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