王者之剑问题

解题思路

本题让我们选一个起点，每一秒都会进行三种操作，综合看来每一秒都能走一步或不走，从而形成各种各样的走法，然后需要求出一种走法使拿走的宝石总价值最大

我们假设这个人并不傻，每走到一个格子，如果格子上有宝石，一定会拿走。

结合题意，偶数秒会使上、下、左、右的格子上的宝石消失，因此得出第一个性质：只能在偶数秒拿宝石。

和第一个性质一样的原理，还能得到第二个性质：不能同时拿走相邻格子上的宝石。如果将相邻两个格子之间都连一条边，则能拿的宝石一定是一个独立集。而每个格子上都有一个权值，又是求获得宝石的最大值，可以发现本题已经非常像最大权独立集问题。

到此已经能将任意一个合法方案对应到二分图中的一个独立集。但是还需要证明任意一个二分图中的独立集都能对应到一个合法方案。其实对于任意一个独立集都能构造出一个合法方案，可以从最左上角的一个有宝石的格子开始走，依次去取别的宝石，假设当前距离下一个宝石还剩两步，停下来判断一下，如果当前是偶数秒，直接走过去拿宝石，如果当前是奇数秒，原地停一秒再走过去拿宝石。且保证每次都优先取最近的宝石。这样的行走方案一定能将独立集中的所有宝石拿走，可以自行按照以上思路证明，这里的构造方式非常多，只要掌握好停顿一秒的精髓就能随便构造。

由此得出任意一个合法方案和任意一个独立集都是一一对应的，因此要想求最大能取的宝石价值就等价于求最大权独立集，而最大权独立集 $=$ 总权值 $-$ 最小权点覆盖集。

具体可参考 最大权点独立集的相关概念

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = 60010, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

int get(int x, int y) //给每个位置一个编号
{
    return (x - 1) * m + y;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点能传输的最大流量，上限是 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //最小割
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; //方向向量

    S = 0, T = n * m + 1; //源点、汇点
    int sum = 0; //记录权值和
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            int x;
            scanf("%d", &x);
            if(i + j & 1) //奇数格作为左部节点
            {
                add(S, get(i, j), x); //从源点向左部节点连一条边，容量是权值
                for(int k = 0; k < 4; k++)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 1 && x <= n && y >= 1 && y <= m)
                        add(get(i, j), get(x, y), INF); //从每个点向相邻节点连一条容量为 INF 的边
                }
            }
            //偶数格作为右部节点
            else add(get(i, j), T, x); //从右部节点向汇点连一条边，容量是权值

            sum += x; //累计权值
        }

    printf("%d\n", sum - dinic()); //最大权独立集 = 总权值 - 最小权点覆盖集

    return 0;
}